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

f(n) = ∏( p_i^2e_i+1+1 ), where p_i is prime factor of n and e_i is highest power of p_i 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 ).