NUMTRY - Number Theory


f(n) and g(n) are two functions defined as following :

f(n) = ( pi2ei+1+1 ), where pi is prime factor of n and ei is highest power of pi in n.

g(n) = Σ( n/gcd(n,i) ); 1 <= i  <= n

For a given value of n, you have to compute [f(n)/g(n)] % 1000000007.

Input

First line has T ( <= 10000 ), next T lines has 2 <= n <= 10^12.

Output

[f(n)/g(n)] % 1000000007 for each test case.

Example

Input:
2
2
4 Output:
3
3

Warning: Test cases aren't random. Test files consist of large primes, strong pseudo primes, Carmichael numbers, squares of primes, product of large primes, worst possible test cases for fermat, miller rabin and other primality testing algorithms.

Note: You may try the tutorial version ( same test files, 5s-100s time limit ). 


hide comments
Francky: 2014-06-07 13:47:00

I did my best with python+psyco, and got tle, I haven't the best algo.
Edit : thanks for the tutorial edition.

Last edit: 2012-03-26 16:15:01

Added by:XeRoN!X
Date:2012-03-23
Time limit:0.100s-1.192s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Number Theory