401939: GYM100589 G Count Permutations

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Count Permutationstime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
2
2 1
3 1
Output
2
2
Note

Example case 1. All permutations are valid.

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

加入题单

上一题 下一题 算法标签: