Count X-Digit Numbers with Specified Digit Sum

You are given two integers X and Y. Your task is to count the number of X-digit numbers such that the sum of their digits is exactly Y. An X-digit number is defined as a number that has exactly X digits and cannot have a leading zero (except when X = 1, where the only digits allowed are 1 to 9).

For example, for X = 2 and Y = 4, the valid numbers are 13, 22, 31, and 40, so the answer is 4.

This problem can be solved using dynamic programming with memoization. If no such number exists, the answer should be 0.

Note: Input is read from standard input and output is written to standard output.

inputFormat

The first line of input contains an integer T, the number of test cases. Each of the following T lines contains two integers X and Y, separated by a space, representing a test case.

outputFormat

For each test case, output a single line containing the count of X-digit numbers whose digits sum up to Y.

## sample

2
2 4
3 6

4
21

</p>