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