Ever since that wicked thief took away some of her murgis (hens, that is), Meena was ever anxious that something similar might happen again someday. Thus, everyday after school, she would step on her yard, and start counting the number of hens she had. Doing this thing tirelessly each day seemed incredibly monotonous to Mithu, and thus he decided to pass his time by solving some problem that he had made up for himself (yeah, that’s right, Mithu could make up problems of his own and even solve 96% of them!).
Mithu likes numbers whose digits are strictly increasing from left to right, for example 158, 123, 14689, etc. Numbers like 1145, 1423 of 7945 are not included among them.
Now, given n and k, Mithu wants to know how many k-digit numbers (without leading zeroes, of course) are there in an n-based number representation, such that the digits of the numbers are strictly increasing. Mithu wants to solve this problems before Meena can finish counting all the murgis, so help him solve it as fast as possible!
Input
The first line of the input contains a single integer T (1 ≤ T ≤ 500), indicating the number of test cases to follow.Each test case contains two space-separated integers n (2 ≤ n ≤ 20) and k (1 ≤ k ≤ 20) in a single line.
Output
For each test case, print the answer in a separate line.
Sample
| Input | Output |
|---|---|
2 2 1 3 1 | 1 2 |
0 is considered to be a number with 0 digits.
