Problem Description

An array P = [$p_1$, $p_2$, ..., $p_n$] is a “n-permutation”, if and only if all pi are in [1, n] and distinct.
For a n-permutation P, we define a transform function F on P: F(X) = [$X_{p_1}$, $X_{p_2}$, ..., $X_{p_n}$]. The result is obviously also a n-permutation.
It is not hard to find that if we apply F on P repeatedly, the result will be same as the original P at certain time. Formally, we define $F^0$(X) = X, and $F^{i+1}$(X) = F($F^i$(X)), then we use G(P) to represent
the minimum positive number which satisfy $F^{G(P)}$(X) == X. (Two n-permutations are equal (“==”), ifand only if their corresponding elements are equal. )
Among all n! different n-permutations, how many distinct values of G are there?

Input

Input is given from Standard Input in the following format:
T
$n_1$
$n_2$
...
...
...
$n_T$
Constraints
1 ≤ T ≤ 3000
1 ≤ n ≤ 3000

Output

Print T line denotes the answers.
Each line contains the number of distinct values of G($P_i$), where $P_i$ enumerates all $n_i$-permutations.
The answer maybe very large, you should modulo 1000000007(10^9 + 7)

3
1
2
3

1
2
3