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 .
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.
For each test case print the required answer in one line.
2
2 1
3 1
2
2
Example case 1. All permutations are valid.
Example case 2. Permutations [1, 2, 3], [3, 2, 1] are counted.