NUMTRYE - Number Theory (Easy)

no tags 

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


Added by:XeRoN!X
Date:2012-03-25
Time limit:1s-13.48s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64