eolymp
bolt
Try our new interface for solving problems
Problems

Binomial coefficients 1

Binomial coefficients 1

Time limit 1 second
Memory limit 128 MiB

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

C_n^{k} = {n! \over k! \cdot (n - k)!} (0 \le k \le n)

You are given the numbers n and k. Calculate C_n^{k}.

Input data

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

Output data

Print t lines, each contains the value C_n^{k} for corresponding test.

Examples

Input example #1
6
0 0
1 0
1 1
2 0
2 1
2 2
Output example #1
1
1
1
1
2
1
Author Anton Lunyov