An arithmetic progression is a sequence of numbers a₁, a₂,... a_n such that a_i+1-a_i is equal for all 0≤i<n. This difference is called the common difference of the arithmetic progression.

Now consider a sequence of arithmetic progressions A₁ = (a_1,1, a_1,2,... a_1,n1), A₂ = (a_2,1, a_2,2,... a_2,n2),... A_k = (a_k,1, a_k,2,... a_k,nk)

A progressive progression is such a sequence with the additional properties that:

• a_i,ni = a_i+1,1 for 1 ≤ i < k
• c_i, the common difference of A_i, is a positive factor of a_i,1 for 1 ≤ i ≤ k
• c_i<c_i+1 for 1 ≤ i < k
• n_i >1 for 1 ≤ i ≤ k
• k ≥ 1

Find the number of progressive progressions such that a_1,1=1 and a_k,nk = N. As this number can be quite large, output it modulo 100000007.

Input

The first line of input contains T (≤ 100), the number of testcases. This is followed by the description of the testcases. The description of each testcase consists of a single integer N (1 < N ≤ 1000000).

Output

For each testcase, output modulo 100000007 the number of progressive progressions such that a_1,1=1 and a_k,nk = N

Example

Input:
2
5
10
Output:
1
6