Binomial coefficients X29864

The binomial coefficient $(N \;\; k)$, $0\leq k\leq N$, is an important concept in mathematics. Formally, $(N \;\; k)$ represents the number of ways to choose a subset of $k$ elements from a set of $N$ elements. For example, there are three ways to choose a subset of $2$ elements from a set $\{a,b,c\}$ of three elements, namely $\{a,b\}$, $\{a,c\}$ and $\{b,c\}$. Hence $(3 \;\; 2) = 3$.

To compute $(N \;\; k)$, it is convenient to use the following recursive formula: $$(N \;\; k) = (N-1 \;\; k-1) + (N-1 \;\; k).$$ The base case given by $(N \;\; 0)=(N \;\; N)=1$ for any $N\geq 0$.

The binomial coefficients can be arranged into Pascal’s triangle:

Each row $N\geq 0$ contains the binomial coefficients $(N \;\; 0),\ldots,(N \;\; N)$, and each element is the sum of the two elements immediately above it.

Input

The input starts with an integer $C$, the number of cases. On each of the following $C$ lines are two integers $N$ and $k$ satisfying $0\leq k\leq N\leq 20$.

Output

For each case, output the binomial coefficient $(N \;\; k)$ on a single line.