Statement : Counting LCM (Hard)

This is the hard version of the problem. The only difference between the easy and hard versions is the constraints on $Z$.

Chef has a favourite number $Z$. He wants to count the number of pairs $(X, Y)$ such that:

• $1 \le X \le Z$

• $1 \le Y \le Z$

• $\text{lcm}(X, Y) > Z$

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.

• The first and only line of each test case contains a single integer $Z$.

For each test case, output in a single line the number of valid pairs $(X, Y)$.

• $1 \le T \le 10^6$

• $1 \le Z \le 10^9$

• The sum of $Z$ over all test cases does not exceed $10^9$.

Input

Output

5
1
3
5
10
20

0
2
10
52
268

Test case $2$:$Z = 3$. The $2$ valid pairs are $(2, 3)$ and $(3, 2)$, both with $\text{lcm}(2, 3) = 6 > 3$.

Test case $3$:$Z = 5$. The $10$ valid pairs are $(2,3)$, $(3,2)$, $(2,5)$, $(5,2)$, $(3,4)$, $(4,3)$, $(3,5)$, $(5,3)$, $(4,5)$, and $(5,4)$.

For example, $\text{lcm}(3, 4) = 12 > 5$ so $(3, 4)$ is valid, while $\text{lcm}(2, 4) = 4 \le 5$ so $(2, 4)$ is not.