Now, they come across a genie who won't let them pass him unless they answer his question correctly.

He wants the value of the expression p*q*r*s which are the answers to 4 questions which he is going to ask.

P = (the no of primes less than or equal to a given integer, n) - 1.

Q = (the sum of primes less than or equal to n) - 2.

R = (the sum of odd primes less than or equal to n) - 1.

S = (the sum of even primes less than or equal to n) - 2.

Give the genie his answer to help them go to the next level. Since the answer can be large output it modulo 10^9 + 7.

Input format:

The first line of input contains t, the number of test cases.

Each line of a test case contains a single integer n.

Output format:

Print t values, the answers to the t testcases, seperated by a line. Since the answer can be large output it modulo 10^9 + 7.

Constraints:

1 <= t <= 10^4

3 <= n <= 10^18