SPOJ MARBLES

Summary

The problem is to choose n marbles from an infinite set containing k different marble colors with at least one of each color. Assume that marbles of equal color can't be distinguished, and the order of the marbles is irrelevant.

Explanation

This problem concerns combinations. Since you need at least one of each marble, the necessary combination is ${\displaystyle {n-1 \choose k-1}}$. The equation is then ${\displaystyle {\frac {n-1!}{(k-1)!((n-1)-(k-1))!}}}$, however, the crux of the problem is that calculating the factorials directly will quickly overflow the largest integer data type. The solution then becomes discovering a way to cancel the terms as you accumulate the answer.

Input

The first line of the input is a number ${\displaystyle T\leq 100}$ representing the number of tests cases, followed by T lines containing two numbers, n and k, where ${\displaystyle 1\leq k\leq n\leq 1000000}$.

2
10 10
30 7


Output

1
475020