Marry 喜欢计算选择两个小于 $m$ 的非负整数 $a$ 和 $b$，使得 $a \times b \pmod m \neq 0$ 的方案数。

记 $f(m)$ 为选择两个小于 $m$ 的非负整数 $a$ 和 $b$，使得 $a \times b \pmod m \neq 0$ 的方案数。

她已经计算了许多不同 $m$ 下的 $f(m)$，现在她对另一个函数 $g(n) = \sum_{m|n} f(m)$ 感兴趣。例如，$g(6) = f(1) + f(2) + f(3) + f(6) = 0 + 1 + 4 + 21 = 26$。她需要你帮她核对答案。

给定 $n$，你的任务是求出 $g(n)$ 对 $2^{64}$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的总数。每个测试用例占一行，包含一个正整数 $n$。

• $1 \le T \le 20000$
• $1 \le n \le 10^9$

输出格式

对于每个测试用例，输出一个整数 $s$，表示 $g(n)$ 对 $2^{64}$ 取模的结果。

样例

输入 1

2
6
514

输出 1

26
328194