Answer \(Q\) queries for the binomial coefficient \(C(n,k)\), the number of ways to choose \(k\) elements from \(n\) distinct elements.

Input

The first line contains \(Q\). Each of the next \(Q\) lines contains \(n\) and k, in this order.

The input satisfies:

• \(1 \le Q \le 20\)
• \(0 \le k \le n \le 66\)
• Every answer fits in a signed 64-bit integer.

Output

For each query, print \(C(n,k)\) on its own line.

Example

Input

2
5 2
10 3

Output

10
120

Explanation

C(5,2)=10 and C(10,3)=120, printed in the same order as the queries.