Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Counting Murgis

By Mesbah · Limits 1s, 512 MB

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

InputOutput
2
2 1
3 1
1
2

0 is considered to be a number with 0 digits.

Discussion

Statistics


65% Solution Ratio

avivillaEarliest, Aug '17

lliimmFastest, 0.0s

aaman007Lightest, 0 B

mdvirusShortest, 173B

Submit

Login to submit

Related Contests

Battle of Brains, 2017 Ended at 2017-08-12 08:10:00 +0000 UTC
Replay of Battle of Brains, 2017 Ended at 2017-08-14 19:00:00 +0000 UTC
Nepal Team Selection Contest 2 for ACM-ICPC Dhaka Regional 2017 Ended at 2017-10-05 18:15:00 +0000 UTC