NOVICE23 - Problem 3

no tags 

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

hide comments
Ahmed AKram: 2012-02-13 21:54:58

many blank lines and spaces in between, take care !

Last edit: 2012-02-13 22:03:47

Added by:Mahesh Chandra Sharma
Date:2011-01-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NSIT Noivce contest #2