Problem G - Great Numbers

In this problem you have to count the number of great numbers of length n. Here a great number must have the following property:

the number must be divisible by all of its decimal digits.
it does not contain any digit greater than 6 (i.e. 15 is a valid great number but 17 is not).

For example 15 is such a great number because it is divisible by both 1 and 5 but 13 is not because it is not divisible by 3.

Input

The first line of the input file contains an integer T (T ≤ 40) which denotes the total number of test cases. The description of each test case is given below:

An integers N (1 ≤ N ≤ 40).

Output

For each case you have to output the number of great numbers in a single line. Print the output modulo 1000007.

Sample Input

2
1
2

Sample Output

6 
10

Problem Setter: Monish Chakrabortty
Special Thanks: Sohel Hafiz
Next Generation Contest 6