Heard of a procedure called sieve of Eratosthenes? Well, implement this:

1. Fill an array num[n] (where 0 ≤ n ≤ 1000) with numbers from 1 to n.
2. Starting with the second entry in the array, set all its multiples to zero.
3. Proceed to the next non-zero element and set all its multiples to zero.
4. Repeat step 3 till u have set up the multiples of all the non-zero elements to zero.
5. At the conclusion of step 4, all the non-zero entries left in the array would be... (obviously) prime numbers, so print out these numbers.

Input

First line consists of number of test cases t (0 ≤ t ≤ 100). The next lines refers to the values of n (0 ≤ n ≤ 1000).

Output

The number of prime numbers up to n with output of each test case separated by a extra line.

Example

Input:
2
5
10

Output:
1
2
3
5

1
2
3
5
7