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^9+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^9+7

Constraints

1<=T<=100

1<=n<=10000000

Example

Input:
1

2
Output:
1