Prime(n) is defined as  number of primes less than equal to n.

Totient(n) is defined as the number of positive integers less than or equal to n that are relatively prime to n.

F(n) = Prime(n) – Totient(n) 

and we don’t like negative values, so if F(n) < 0, consider it as 0.

G(n) = Totient(n)^{(Factorial (F(n)))}

You are given a number n. You have to output G(n) % 10⁹+7.

Input

First line consists of T, the number of test cases.

Each of the next T lines contains one integer n.

Output

Output T lines each line containing the value of function G(n) % 10⁹+7

Constraints

1 ≤ T ≤ 100

1 ≤ n ≤ 10000000

Example

Input:
1
2

Output:
1