Recently, Misha at the IT Campus "NEIMARK" camp learned a new topic — the Euclidean algorithm.

He was somewhat surprised when he realized that $$$a \cdot b = lcm(a, b) \cdot gcd(a, b)$$$, where $$$gcd(a, b)$$$ — is the greatest common divisor (GCD) of the numbers $$$a$$$ and $$$b$$$ and $$$lcm(a, b)$$$ — is the least common multiple (LCM). Misha thought that since the product of LCM and GCD exists, it might be interesting to consider their quotient: $$$F(a,b)=\frac{lcm(a, b)}{gcd(a, b)}$$$.

For example, he took $$$a = 2$$$ and $$$b = 4$$$, computed $$$F(2, 4) = \frac{4}{2} = 2$$$ and obtained a prime number (a number is prime if it has exactly two divisors)! Now he considers $$$F(a, b)$$$ to be an interesting ratio if $$$a \lt b$$$ and $$$F(a, b)$$$ is a prime number.

Since Misha has just started studying number theory, he needs your help to calculate — how many different pairs of numbers $$$a$$$ and $$$b$$$ are there such that $$$F(a, b)$$$ is an interesting ratio and $$$1 \leq a \lt b \leq n$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^3$$$). The description of the test cases follows.

A single line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^7$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^7$$$.

Output

For each test case, output the number of interesting ratios $$$F(a, b)$$$ for pairs satisfying $$$1 \leq a \lt b \leq n$$$.

Interesting Ratio

Examples