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 ?

For integers m and n, it is said that m divides n, m is a divisor of n, or n is a multiple of m, and this is written as m | n,

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