Problem Description

Multiple query, for each n, you need to get
n i-1
∑ ∑ [gcd(i + j, i - j) = 1]
i=1 j=1

Input

On the first line, there is a positive integer T, which describe the number of queries. Next there are T lines, each line give a positive integer n, as mentioned above.
T<=1e5, n<=2e7

Output

Your output should include T lines, for each line, output the answer for the corre- sponding n.

4
978
438
233
666

194041
38951
11065
89963