The Aliens have taken over NSIT. Our 4^th years are trying to hack the alien worships’ control network. They have been able to figure out that the password used by the aliens is dynamically changing. To access the main controller, we need to enter a key which is to be computed each time using a number displayed on the controller screen.

The scheme used by the aliens is as follows.

For a given number k, the key is the smallest number n, such that,

n%2 = 1, n%3 = 2, n%4 = 3, n%5 = 4 ... n%(k-1) = k-2 and n%k = k-1

Your task is simple. Help the 4th years save NSIT from the aliens, by computing the key value for every given k.

PS: They are very smart btw. Might not need your help at all. :P

Input

First line of input will contain an integer t, the number of testcases. Following t lines will contain an integer k, 1 per line.

Output

For each integer k, output an integer n, such that it follows the aforementioned scheme. Output the answer modulo 1000000007.

t <= 1000

2 <= k <= 100

Example

Input:
3
2
4
7

Output:
1
11
419