A nice sequence is a sequence of digits in which a digit d is placed at any index iff d is 0 or any divisor of d(except 1)  has been placed already. First digit can be anything from 1 to 9.

Find the number of nice sequences of length n.

Input

Input consists of number of test cases t
Following t lines have a single line containing  n as described in the problem statement.

Output

Print the number of nice sequences of length n modulo 1000000007  in a seperate line .

Example

Input:
2
1
2
Output
9
23

Explaination :
For n=2 nice sequences are :

10,20,22,24,26,28,30,33,36,39,40,44,48 and so on !

Constraints:

1<=n<=1000