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 integer 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