748. MARBLES

0

Medium

Hänschen has a dream where he finds himself in a shop with an infinite supply of marbles. He is allowed to choose **n** marbles from the shop, which has marbles of **k** different colors. There are infinitely many marbles of each color. Hänschen wants to ensure that he selects at least one marble of each color, but there are numerous possibilities for his selection. Before he can make a decision, he wakes up. Now, he seeks your help in determining the number of possible selections he could have made. It is important to note that marbles of the same color cannot be distinguished, and the order of the marbles is irrelevant.

Input Format

The first line of input contains an integer 'T' indicating the number of test cases to follow. Each test case consists of a single line containing two integers, 'n' and 'k', where 'n' represents the number of marbles Hänschen selects and 'k' represents the number of different colors of the marbles.

Output Format

For each test case, print the number of possible selections Hänschen could have made. It can be assumed that this number exceeds the limit of a signed 64-bit integer.

Example

Input

2
10 10
30 7

Output

1
475020

Constraints

1<=T<=100

1<=k<=n<=1000000

1<=k<=n<=1000000

Loading...

View Submissions

Console