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 upto 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