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¹².

Output

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

Example

Input:
2
2
4

Output:
3
3