Problem Description

Jo loves his teammate Ky's rick and roll! But he more than loves counting.

Jo thinks, for two numbers $n$ and $d$ ( $d$ is a factor of $n$ ), $d \in Good_n$ if and only if the prime factor set of $d$ $\textbf{equals}$ to that of $n$. That is, $Good_n=\lbrace d\mid n\bmod d=0\wedge \forall p\in Prime\to (d\bmod p=0\leftrightarrow n\bmod p=0)\rbrace $.

For example, $Good_{12}=\lbrace 6, 12\rbrace $ , since the factors of $12$ are $\lbrace 1, 2, 3, 4, 6, 12\rbrace $. $\lbrace 2, 3\rbrace $ are prime factors of $12$, so all its factors of their good factors must contain prime factors $2, 3$. Therefore, only $6, 12$ satisfy the condition.

For a number $n$, Jo will select a factor $d$ randomly from $Good_n$ with equal possibility. if $d=n$, then the rich Jo will pay you $n$ yuan as reward. Otherwise, you will gain nothing.

Ky, the man who treats money as dirt, wants to choose an integer from $[1, M]$ randomly for Jo's game. Help Ky calculate the expectation of money he can get.

Input

The first line contains an integer $T(T≤12)$ . Then $T$ test cases follow.

For each test case, there is only one integer $M(1\leq M\leq 10^{12})$.

It's guaranteed that there are at most $6$ cases such that $M>10^6$ .

Output

For each test case, output one integer in a single line --- the expectation of the money Ky can get.

Since it can be too large, print it modulo $4179340454199820289(=29\cdot 2^{57}+1)$.

1
4

2

Hint

$Good_1=\lbrace1\rbrace $

$Good_2=\lbrace2\rbrace $

$Good_3=\lbrace3\rbrace $

$Good_4=\lbrace2, 4\rbrace $

Therefore, the answer is $\displaystyle {1\over 4}({1\over |Good_1|}+{2\over |Good_2|}+{3\over |Good_3|}+{4\over |Good_4|})={1\over 4}({1\over 1}+{2\over 1}+{3\over 1}+{4\over 2})=2$