Binomial coefficients 1

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

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

Input

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

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

Examples