TECHLN2 - First Blood

no tags 

The Aliens have taken over NSIT. Our 4th 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


Added by:Tarun Gehlaut
Date:2013-04-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CSI NSIT