PRIMEN1 - Sieve Of Erasthosthenes

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

Added by:kousik
Date:2013-09-14
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.