Your task is extremely simple, for a given number N you have to find the smallest number which is divisible by all numbers from 1 to N without leaving any remainder. As the number can be very large print the answer modulo 1000000007.

Input

Input starts with a positive integer T < 501 in a single line, then T lines follow. Each of the T lines contains one positive integer N < 10001.

Output

For every N print the desired number.

Example

Input:
1
5

Output:
60