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_ii+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 test cases. This is followed by the description of the test cases. The description of each test case consists of a single integer N (1 < N ≤ 1000000).

Output

For each test case, 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