Problem Description

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.
---Wikipedia

Today, LIS takes revenge on you. You mission is counting how many permutation of 1-N has a LIS value equals K.

Input

The first line contains a single integer T, indicating the number of test cases.

Each test case only contains two integers, N and K.

[Technical Specification]
1. 1 <= T <= 200
2. 1 <= K <= N <= 18

Output

For each test case, output the number of eligible permutation.

3
3 1
3 2
3 3

1
4
1

Hint

The possible permutations of 1, 2, 3 are [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1].
And their LIS values are 3, 2, 2, 2, 2 and 1, successively.