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 ab.
As the answer can be pretty large (even larger than Manu's Confusions:) ), print it modulo 109+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<=107
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.
For n=6
a=5 and b=7
ab % (109 +7) = 78125
For n=3
a=b=3
ab % (109 +7) = 27
