PROGPROG - Progressive progressions

no tags 

An arithmetic progression is a sequence of numbers a1, a2,... an such that ai+1-ai is equal for all 0≤i

Now consider a sequence of arithmetic progressions A1 = (a1,1, a1,2,... a1,n1), A2 = (a2,1, a2,2,... a2,n2),... Ak = (ak,1, ak,2,... ak,nk)

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

  • ai,ni = ai+1,1 for 1 ≤ i < k
  • ci, the common difference of Ai, is a positive factor of ai,1 for 1 ≤ i ≤ k
  • cii+1 for 1 ≤ i < k
  • ni >1 for 1 ≤ i ≤ k
  • k ≥ 1

Find the number of progressive progressions such that a1,1=1 and ak,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 a1,1=1 and ak,nk = N

Example

Input:
2
5
10

Output:
1
6


Added by:Raziman T V
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IOPC2011