E. Counting Binary Strings
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Patrick calls a substring$$$^\dagger$$$ of a binary string$$$^\ddagger$$$ good if this substring contains exactly one 1.

Help Patrick count the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Note that substrings are differentiated by their location in the string, so if $$$s =$$$ 1010 you should count both occurrences of 10.

$$$^\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$$$^\ddagger$$$ A binary string is a string that only contains the characters 0 and 1.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2500$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2500$$$, $$$1 \leq k \leq n$$$) — the number of required good substrings and the maximum allowed length of a good substring.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2500$$$.

Output

For each test case, output a single integer — the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Since this integer can be too large, output it modulo $$$998\,244\,353$$$.

Example
Input
6
1 1
3 2
4 2
5 4
6 2
2450 2391
Output
1
3
5
12
9
259280854
Note

In the first test case, the only suitable binary string is 1. String 01 is not suitable because it contains a substring 01 with length $$$2 > 1$$$.

In the second test case, suitable binary strings are 011, 110 and 111.

In the third test case, suitable binary strings are 101, 0110, 0111, 1110, and 1111.