Vaibhav loves playing with numbers. To enjoy his summer holidays he decides to join the group "number players" of his school. He decides to visit the group hall. At the gate he finds a lock and a paper. The gate can only be unlocked by solving the puzzle written on the paper. Vaibhav is stuck with his puzzle, help him in solving it.

Here is the puzzle description:

Given a sequence F(N)

F(0) = 1
F(1) = 1
F(2) = 1
F(n) = product of all odd primes less than or equal to n (for n<=10)
F(n) = (2^(n/4)) * F(n/5)* F(n/10)      (for n>10)

For every fraction, a ceil value is taken for evaluation.

For eg. F(11)=2^ceil(11/4) * F(ceil(11/5)) * F(ceil(11/10))  = 2^3 * F(3) * F(2) = 24

Given N. Find the max value of (a^b)%mod such that a and b satisfies the relation gcd(a,b) = F(N).

Gcd : Greatest common divisor

Input

First line gives T, total number of test cases.

Next T line gives number N

Output

For each test case, print the desired value on a new line

Constraints

T<=10

N<=10^6

mod = 10^9.

NOTE: a must be <= 5*F(n) and b must be <=5*F(n), a can be equal to b and mod=10^9

Example

Input:
1
2

Output:
1024