老八想要统计这样的 \((a,b)\) 有多少对：

• $1\leq a\leq b\leq n$
• \(\gcd(a,b)=a\texttt{ xor }b\)

老八初学编程，只会计算 \(n\leq 10^3\) 时的答案。

请你帮忙写个程序计算 \(n\leq 3\times 10^{7}\) 的答案。

第一行一个整数 \(T\) ，接下来 \(T\) 行每行一个整数 \(n\) 。

每行一个整数答案。

样例1

样例输入

2
7
20000000

样例输出

4
34866117

样例解释
\(n=7\) 时符合要求的 \((a,b)\) 有 \((2,3),(4,5),(4,6),(6,7)\) 。

数据范围

对于20%的数据， $1\leq T\leq 10$ ， $1\leq n\leq 10^3$ ；

对于60%的数据， $1\leq T\leq 10^4$ ， $1\leq n\leq 10^6$ ；

对于100%的数据， $1\leq T\leq 10^4$ ， $1\leq n\leq 3\times 10^7$ 。