Gopi is fond of sandwiches. Once his friend asks him to give part of his sandwich. But, Gopi wants to give him as little sandwich as possible. So, he devises a method.

He divides the sandwich into n parts, where each part is a unit fraction (fractions of the form 1/p where p is integer) of the original sandwich. Among all these parts he chooses the smallest part and gives it to his friend. Help Gopi to find the smallest part possible.

Input

First line contains t (1 <= t <= 10⁵) the number of test cases. The next t lines contain one integer per line denoting n (2 <= n <= 10⁶) the number of parts the sandwich can be divided.

Output

Output one line per test case containing the denominator of the smallest part. Since, the answer can be very large, print the answer modulo 10⁹ + 7.

Example

Input:
1
3

Output:
6

Explanation:

The possible ways of dividing the sandwich into 3 parts are:

• 1/3, 1/3, 1/3
• 1/6, 1/2, 1/3
• 1/4, 1/4, 1/2

Among these, the second way has the smallest part. Hence the output is 6.