Asha is an aspiring mathematician. One day she discovered numbers that she calls prosperous numbers. A prosperous number is a positive integer such that its every digit is greater than or equal to the digit preceeding it (if it exists). The first prosperous number is 1. Notice that this means that none of the prosperous numbers may contain the digit 0. She defines the following attributes of these numbers -

a) degree - the maximum difference of two consecutive digits of the prosperous number.

b) strength - the sum of all digits of the number

For example - some of the prosperous numbers with their degree and strength are:

Prosperous number Degree Strength
5 0 5
28 6 10
399 6 21
444 0 12
5789 2 29
12345 1 15

You are helping her find the number of prosperous numbers that exist given the degree and strength.

Input Format :
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line with two integers, S and D, which represent the strength and degree respectively.

Output Format:
For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then, for every test case, output the total number of possible prosperous numbers of strength S and degree D. Because this number can be quite large, you only need to print the answer modulo 1000000007.

Constraints:
0 < T ≤ 20

0 < S ≤ 10^5

SAMPLE INPUT
4
2 0
10 1
12 4
15 8

SAMPLE OUTPUT
Case #1: 2
Case #2: 11
Case #3: 9
Case #4: 1

Explanation

For the first test case, there are two possible prosperous numbers - 2 and 11.

For the second test case, there are eleven possible prosperous numbers - 334, 1234, 2233, 11233, 12223, 111223, 112222, 1111123, 1111222, 11111122 and 111111112.

For the third test case, there are nine possible prosperous numbers - 48, 156, 237, 1137, 1155, 2226, 11226, 111126 and 11111115.

For the fourth test case, there is only one possible prosperous number - 1111119.

见题面

见题面