L. Landau's Fourth Problem
time limit per test
11 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

It is the year 1912 and you are in the United Kingdom, attending the Fifth International Congress of Mathematicians (ICM). The internet, League of Legends, and Geosé don't exist yet... what a wonderful world!

Sir Abraham Marckess and Sir Feet Tester (Yes, that name is actually pretty common in Zacateland, the city he is from) are two assistants to the brilliant mathematician Edmund Landau.

Landau is about to present four fundamental problems related to prime numbers at this congress. What they don't yet know is that the year 2026 will arrive and these problems will still remain unsolved. Mr. Landau already has the first three prepared, but for the last one, he still has some things to verify. The problem is:

Do there exist infinitely many prime numbers $$$p$$$ such that $$$p-1$$$ is a perfect square?

Or said more simply:

Let $$$f(n) = n^2 + 1$$$ with $$$n \ge 1$$$. Do there exist infinitely many primes generated this way?

Since computers as we know them today didn't exist back then, and Landau didn't want to look incompetent at the congress, he needed to verify empirically that his proposal was correct at least up to a very large number.

Thus, Landau tasked Sir Marckess and Sir Tester with the enormous task of calculating how many $$$f(n)$$$ are truly primes up to a given $$$N$$$. However, not trusting their abilities completely, Landau decided to test them by posing this question through many queries.

Your mission is to help Sir Marckess and Sir Feet Tester answer them all correctly before the conference begins.

Input

The first line contains a single integer $$$Q$$$ ($$$1 \le Q \le 4 \times 10^6$$$), the number of queries.

The next $$$Q$$$ lines each contain an integer $$$N$$$ ($$$1 \le N \le 7 \times 10^7$$$).

Output

For each query, print a single integer: the count of values $$$n$$$ in the range $$$1 \le n \le N$$$ for which $$$f(n) = n^2 + 1$$$ is prime.

Example
Input
3
10
100
1000
Output
5
19
112
Note

For the first query ($$$N = 10$$$): $$$f(n) = n^2 + 1$$$ for $$$n \in \{1, 2, \ldots, 10\}$$$ yields the values $$$\{2, 5, 10, 17, 26, 37, 50, 65, 82, 101\}$$$. Among these, the primes are $$$\{2, 5, 17, 37, 101\}$$$, for a total of 5.