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