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