2015 CodeCraft IIIT Hyderabad Replay |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/08/2023 21:30:16 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|