Manu, the girl of confusion has a simple problem to solve but she got confused about how to solve it. Can u help her solve it?

You are given a number n. You have to find the largest prime number <= n (say a) and the smallest prime number >= n (say b).

You are supposed to find a^b.

As the answer can be pretty large (even larger than Manu's Confusions:) ), print it modulo 10⁹+7.
 

Input Format:
First line contains the number of test cases t. 
Next t lines conatins a single integer n as described in question.

Output Format:
For each test case, print a single line containing the answer
 

Constraints:
t<=10⁷
2<= n <=9999991

P.S. - The test cases for the problem are too tight. Use fast I/O and all possible optimisations to get AC.