G. Count Permutations
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given N and K, count number of permutations of [1, 2, 3...N] in which no two adjacent elements differ by more than K. For example, permutation [4, 1, 2, 3] cannot be counted for .

Input

First line contains T(1 ≤ T ≤ 10), the number of test cases. Each test case consists of N(1 ≤ N ≤ 15) and K(0 ≤ N) in single line.

Output

For each test case print the required answer in one line.

Examples
Input
22 13 1
Output
22
Note

Example case 1. All permutations are valid.

Example case 2. Permutations [1, 2, 3], [3, 2, 1] are counted.