Now, your task is to calculate the numbers of the prime numbers between 1 and an integer N.
The input file contains several cases. The first line contains an integer T ( 1 <= T <= 1,000) represent the number of cases. The next T lines, there will be an integer N ( 1 <= N <= 1,000,000) on a single line.
Please output the number of prime numbers between 1 and N.