For each query, compute \(S(n,k)\), the number of ways to partition \(n\) distinct elements into exactly \(k\) non-empty unlabeled subsets.

Input

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

The input satisfies:

• \(1 <= Q <= 100\)
• \(1 <= k <= n <= 25\)

Output

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

Example

Input

3
2 1
7 3
9 3

Output

1
301
3025