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.