Jo 喜欢他的队友 Ky 的摇滚乐！但他更喜欢计数。

Jo 认为，对于两个数 $n$ 和 $d$（$d$ 是 $n$ 的因子），当且仅当 $d$ 的质因子集合与 $n$ 的质因子集合相等时，称 $d$ 是 $n$ 的“好因子”。即 $Good_n = \{d \mid n \bmod d = 0 \land \forall p \in Prime \to (d \bmod p = 0 \leftrightarrow n \bmod p = 0)\}$。

例如，$Good_{12} = \{6, 12\}$，因为 $12$ 的因子是 $\{1, 2, 3, 4, 6, 12\}$。$\{2, 3\}$ 是 $12$ 的质因子，因此 $12$ 的所有好因子必须包含质因子 $2$ 和 $3$。因此，只有 $6$ 和 $12$ 满足条件。

对于一个数 $n$，Jo 将从 $Good_n$ 中等概率地随机选择一个因子 $d$。如果 $d = n$，那么富有的 Jo 将支付给你 $n$ 元作为奖励。否则，你将一无所获。

Ky，这个视金钱如粪土的人，想要从 $[1, M]$ 中随机选择一个整数 $n$ 来进行 Jo 的游戏。请帮助 Ky 计算他能获得的金钱期望值。

输入格式

第一行包含一个整数 $T(T \le 12)$。接下来有 $T$ 组测试数据。 对于每组测试数据，只有一个整数 $M(1 \le M \le 10^{12})$。 保证满足 $M > 10^6$ 的测试数据不超过 $6$ 组。

输出格式

对于每组测试数据，输出一行一个整数，表示 Ky 能获得的金钱期望值。 由于结果可能非常大，请输出其对 $4179340454199820289(= 29 \cdot 2^{57} + 1)$ 取模的结果。

样例

输入 1

1
4

输出 1

2

说明

$Good_1 = \{1\}$ $Good_2 = \{2\}$ $Good_3 = \{3\}$ $Good_4 = \{2, 4\}$

因此，答案是 $\frac{1}{4}(\frac{1}{|Good_1|} + \frac{2}{|Good_2|} + \frac{3}{|Good_3|} + \frac{4}{|Good_4|}) = \frac{1}{4}(\frac{1}{1} + \frac{2}{1} + \frac{3}{1} + \frac{4}{2}) = 2$。