Problem A
Animal Cracker Monday

On Animal Cracker Monday (ACM for short), you are given a number of animal crackers, n. Each animal cracker is labeled with a number ranging from 1 to n. You must eat at least one animal cracker, but you cannot eat any two animal crackers that share a digit in their numeric representation. How many different ways can some set of animal crackers be eaten such that the number associated with any two animal crackers does not have any individual digits in common?

For example, if n = $12$, there are $14$ animal crackers marked $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $11$, and $12$ respectively. Crackers $3$, $5$, and $9$ are allowed to be eaten together. Animal crackers $2$, $7$, $8$, and $11$ can also be eaten together. However, crackers $2$, $7$, and $12$ cannot be eaten together because crackers $2$ and $12$ have the digit $2$ in common.

Note: the ordering of animal crackers in each set is inconsequential. Therefore, eating animal crackers $(7, 8, 9)$ is the same as eating animal crackers $(9, 8, 7)$.

Input

The first input line is a number $N$ ($0 \leq N \leq 20$) which corresponds to the number of test cases. Each of the following N lines is a single test case, containing an integer $I$ ($1 \leq I \leq 10^9$). So, if N = $11$, there are $11$ lines following the first line, each with a single test case $I$.

Output

For each test case, output the test case number associated with that test case and follow it with the number of sets of animal crackers modulo $1000000007$.

4
7
8
9
10

Case 1: 127
Case 2: 255
Case 3: 511
Case 4: 767

3
679
5019
2609

Case 1: 158286063
Case 2: 640658343
Case 3: 397337905

4
174
956
4072
8993

Case 1: 4911233
Case 2: 561134599
Case 3: 283097892
Case 4: 201022736