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∈Goodn if and only if the prime factor set of d equals to that of n. That is,
Goodn={d∣nmodd=0∧∀p∈Prime→(dmodp=0↔nmodp=0)}.
For example,Good12={6,12} , since the factors of 12 are {1,2,3,4,6,12}. {2,3} 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 Goodn 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.
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≤M≤1012).
It's guaranteed that there are at most 6 cases such that M>106 .
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*257+1).
1
42
Good1={1}
Good2={2}
Good3={3}
Good4={2,4}
Therefore, the answer is (∣Good1∣1+∣Good2∣2+∣Good3∣3+∣Good4∣4)=1/4(1/1+1/2+1/3+2/4)=2