Binomial coefficients 1#318
Sign in

Binomial coefficients 1

1 second
128 megabytes
Easy

Let be a non-negative integer. Define n! = 1 \cdot 2 \cdot \ldots \cdot n (0! = 1), and

C_n^{k} = \frac{n!}{k! \cdot (n - k)!} \quad (0 \leq k \leq n)

Given and , calculate C_n^{k}.

Input

The first line contains the number of test cases (t \leq 50). Each of the next lines contains two integers and (0 \leq n < 2^{64},\ 0 \leq C_n^{k} < 2^{64}).

Output

Print lines, each containing the value C_n^{k} for the corresponding test case.

Examples

Example 1

Loading
Loading