355. 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. However, 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 from each other, and the order of the marbles is not significant.

Input Format

The first line of the input consists of a number 'T' which represents the number of test cases to follow. Each test case is presented on a separate line and contains two integers, 'n' and 'k', where 'n' is the number of marbles Hänschen selects and 'k' is the number of different colors of the marbles.

Output Format

For each test case, print the number of possible selections that Hänschen could have made. It is 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