Now you all helped Vaibhav solve the puzzle and open the gate last time (although not too much help). But as soon as he opens the gate, there is another puzzle to open the front door. Let’s see whether this time you all are able to help him or not.

• Fac(n) = number of trailing zeroes in n!
• Fact(n) = Fac(n) % 25 + 1
• 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) = 4^fact(n) × f(n/5) × f(n/10) (for n > 10)

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

For eg. F(11) = 4^fact(11) × F(floor(11/5)) × F(floor(11/10)) = 4³ × F(2) × F(1) = 64

Given N, find the maximum 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 lines give the number N.

Output

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

Constraints

T ≤ 10

N ≤ 10⁶

mod = 10⁹

NOTE: a must be ≤ 5 × F(n) and b must be ≤ 5 × F(n), a can be equal to b.

Example

Input:
1
2

Output:
1024