CF1920E.Counting Binary Strings

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.

帕特里克将一个二进制字符串的子串$^\dagger$称为“好”的，当且仅当该子串中恰好包含一个 1。

请帮助帕特里克计算满足以下条件的二进制字符串 $s$ 的个数：

• $s$ 中恰好包含 $n$ 个好子串；
• $s$ 中不存在长度严格大于 $k$ 的好子串。

注意：子串由其在字符串中的位置区分。例如，若 $s = $ 1010，则应将两个 10 均计入（即分别对应位置 $[0,1]$ 和 $[2,3]$）。

$^\dagger$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可通过从 $b$ 的开头删除若干（可能为零或全部）字符、并从 $b$ 的末尾删除若干（可能为零或全部）字符而得到。
$^\ddagger$ 二进制字符串是仅由字符 0 和 1 组成的字符串。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 2500$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅一行，包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2500$，$1 \leq k \leq n$），分别表示所需“好子串”的数量以及“好子串”允许的最大长度。

保证所有测试用例中 $n$ 的总和不超过 $2500$。

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$.

对于每个测试用例，输出一个整数——满足以下条件的二进制字符串 $s$ 的个数：$s$ 恰好包含 $n$ 个“好”子串，且不包含长度严格大于 $k$ 的“好”子串。由于该整数可能过大，请将其对 $998\,244\,353$ 取模后输出。

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 \gt 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.

在第一个测试用例中，唯一合适的二进制字符串是 1。字符串 01 不合适，因为它包含长度为 $2 \gt 1$ 的子串 01。

在第二个测试用例中，合适的二进制字符串有 011、110 和 111。

在第三个测试用例中，合适的二进制字符串有 101、0110、0111、1110 和 1111。