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 separate line.

Example

Input
2
1
2

Output
9
23

Explanation

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