Lady Layton has a problem about math.

She will give you a integer n, please calculate .

输入描述:

The first line contains one integer T(1<=T<=10)— the number of test cases.
The only line of each test case contains one integers n() — the integer of she give.

输出描述:

For each test case print the answer modulo  in one line.

3
10
100
1000

136
21012
2914160

备注:

In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, .
In number theory,  be called Euler's phi function, it is the number of integers k (1<=k<=n) which .