Competitions
Биномиальный коэффициент
Binomial coefficients 1
Let n be a non-negative integer. Let n! = 1 * 2 *... * n (0! = 1) and
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 ≤ 50). Each of the next t lines contains two integers n and k (0 ≤ n < 2^64, 0 ≤ 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