# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Left Prime

Limits: 1s, 128 MB

Prime numbers are the ones which can only be divided by 1 and the number itself. **2, 3, 5, 7, 11, 13** etc.
are prime numbers.

In this problem, you will take a number **N** as input and print the total number of prime numbers that are in the left of **N**.

#### Input

In the first line of input, you will take a number **T ( 1 ≤ T ≤ 10 ^{5} )**. It indicates the total number of testcases. In the following

**T**lines, you will take a number

**N ( 1 ≤ N ≤ 10**as input and print the total number of prime numbers that are in the left of

^{ 7})**N**.

#### Output

For each test case print the ans of the corresponding **N** in a newline.

#### Samples

Input | Output |
---|---|

5 1 2 3 4 5 | 0 0 1 2 2 |

#### tahmedge

→