You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 64.0 MB

Description

In the ancient kingdom of Numeria, the royal mathematician loved symmetry and harmony in numbers.
He believed that the strength of a pair of soldiers in the army could be measured by the harmony between their ranks.

Each soldier in the army has a unique rank from \(1\) to \(N\). The mathematician defines a pair of soldiers \((i, j)\)
to be perfectly harmonious if:

• \(1 ≤ i ≤ j ≤ N\)
• \(gcd(i, j) = |i - j|\)

Here, '\(gcd\)' means greatest common divisor, and '\(| |\)' represents the absolute value.

The king has asked you, the lead royal coder, to help determine how many such perfectly harmonious pairs of soldiers exist in the army of size \(N\).

Note : The only difference between the easy and hard versions is the constraint on \(T\) and \(N\).

Input

• The first line contains a single integer \(T\) (\(1 ≤ T ≤ 10^3\)) — the number of test cases.
• The next \(T\) lines each contain a single integer \(N\) (\(1 ≤ N ≤ 10^9\)).

Output

• For each test case, output a single line containing the number of harmonious pairs (i, j) that satisfy the conditions.

Sample

4
4
5
1000
2000000

4
5
6069
27326296

For N = 4, the harmonious pairs (i, j) that satisfy 1 ≤ i ≤ j ≤ 4 and gcd(i, j) = |i - j| are:

(1, 2): gcd(1, 2) = 1, |1 - 2| = 1 — harmonious

(2, 3): gcd(2, 3) = 1, |2 - 3| = 1 — harmonious

(2, 4): gcd(2, 4) = 2, |2 - 4| = 2 — harmonious

(3, 4): gcd(3, 4) = 1, |3 - 4| = 1 — harmonious

So, the total number of perfectly harmonious pairs is 4.