SPOJ Brasil

Given an integer 'N', print count all the prime numbers which are less than or equal to 'N'.

Input description

First line of input is an integer T (number of testcases) and integer T will be followed by T lines, where each line will contain an integer N.

Output description

Output will consists of T lines. Each line will have count of prime numbers not greater than 'N'.

Constraint

1<=T<=10000

1<=N<=1000000

Example

Input:
2
9
11

output
4
5