You have N cards and each has an unique number between 1 and N written on it. In how many ways can you select a non-empty subset of the cards such that the number written on any two of your selected cards don’t have any common digits? For example, when N = 12, {1, 2, 3}, {2, 11}, {3, 4, 5, 6, 7, 8, 9, 12} are some valid selections. But {1, 2, 10}, {2, 5, 12} are not allowed. Input The first line of the input contains an integer T (T ≤ 15) which is the number of test cases. Each of the following T lines denote a test case, containing an integer N (1 ≤ N < 109). Output For each test case, output the case number followed by the number of subsets modulo 1000000007. Sample Input 2 3 12 Sample Output Case 1: 7 Case 2: 1151