For a given positive integer N, you have to find how many prime numbers are there up to N.

Input

First line contains T the number of test cases, (about 1000). Each of next T lines contains 1 integer N (1<=N<=1000000).

Output

For each test case print the answer in a new line.

Example

Input:
2
5
10

Output:
3
4