The problem statement has recently been changed. View the changes.

×
G. Count Permutations

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputGiven *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

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.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2022 00:39:36 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|