Daenarys Stormborn is preparing to free a new city from slavery.In order to do so she and her army has to clear the barrier of a big wall of length n.For clearing the wall she creates a stair of length n joinning smaller stairs.The length of smaller stairs can only be unequal primes.If the number of ways she can create stair of length n is 'a' then b is a mod 1000000007.And p is the largest prime factor of b. Her dragons demand her to break p as sums of q1,q2â€¦qk(for any k > 0) i.e. q1+q2+....+qk=p, such that q1,q2...qk have largest possible GCD. If more than one such set exists then take the set in which q1,q2...qk have largest product .GCD of single number is 1 . Report (Product of q1,q2....qk) mod 1000000007. If the number of ways modulo m ie. b = 0 or 1 report 0 .
Input- First Line contains t, number of test cases. Followed by t lines each containing an integer n, the length of wall .
Output- Report the value of (Product of q1,q2....qk) mod 1000000007 as asked above.
Constraints- 0 < t <= 10 4 < n < 1200
Example- Input- 2 5 6
Output- 2 0
Explanation- 5=2+3 or 5 Thus a=2 Thus b=2(2 mod 1000000007) Thus p=2(Largest prime factor of b) Thus possible sets of qi 's with largest GCD (1,1) or (2) Thus one with largest Product is 2