Bertrand's postulate

Bertrand's postulate is a theorem stating that for any integer n > 1, there always exists at least one prime number p that is between n and 2n .
You are asked to solve a more challenging task. Given a number n, you should answer questions like how many prime numbers p are there such that n < p < 2n.

Input

The first line of the input contains a single integer t (1 ≀ t ≀ 100) the number of test cases.
The next t lines contain a single integer n (2 ≀ n ≀ 500 000).

Output

The program should print the number of primes between n and 2n for each test case on separate lines.

Examples

Input
Output
2 2 239
1 39
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue