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⁵