Find the number of pairs of non negative integers(n,m),such that 1 ≤ n<m ≤ k, where 2 ≤ k ≤ 1000000 and n|m^2 - 1 and m|n^2 - 1 ?

Input :
first line conatins number of test case “T” and then T lines follows.
Each test case contains one integer "k".

Output:

For each test case print the number of pairs of non negative integers(n,m).

Constraints:
1 ≤ T ≤ 10
2 ≤ k ≤ 1000000

Sample input:
3
10
40
49

Ouptut:
18
82
101
Register for IndiaHacksSAMPLE INPUT
9
1000000
456
789
2
234
94
10
100
5

SAMPLE OUTPUT
2001159
937
1614
1
485
195
18
208
7

Register for IndiaHacks

见题面

见题面