CF2091E Interesting Ratio

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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of the numbers $ a $ and $ b $ and $ lcm(a, b) $ — is [the least common multiple (LCM)](https://en.wikipedia.org/wiki/Least_common_multiple). 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 < 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 < b \leq n $ ?

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 $ .

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