Problem F
Taco Tuesday

You are given a number of tacos, n. Each taco is labeled with a number ranging from 1 to n. You must eat at least one taco, but you cannot eat any two tacos whuch share a digit in their numbered representation. How many different ways can some grouping of tacos be eaten such that the number associated with any two tacos does not have any individual digits in common?

For example, if n = 14, there are 14 tacos marked 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, and 14 respectively. Tacos 2, 5, and 8 can be eaten together. Tacos 3, 7, 9, and 11 can also be eaten together. However, tacos 1, 8, and 14 cannot be eaten together because tacos 1 and 14 have the digit "1" in common.

Note: the ordering of the tacos in each grouping is inconseqential. Therefore, eating tacos 1, 2, and 3 is the same as eating tacos 2, 3, and 1.

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 groupings of tacos modulo 1000000007.

2
6411
6990

Case 1: 917853798
Case 2: 575512092

3
763
4342
8476

Case 1: 215415887
Case 2: 700571404
Case 3: 315828143