如果二进制字符串 $$$^\ddagger$$$ 的子字符串 $$$^\dagger$$$ 正好包含一个 1,则 Patrick 称此子字符串为好。
帮助 Patrick 计算二进制字符串 $$$s$$$ 的数量,使得 $$$s$$$ 恰好包含 $$$n$$$ 好子串,并且没有长度严格大于 $$$k$$$ 的好子串。请注意,子字符串根据其在字符串中的位置进行区分,因此如果 $$$s =$$$ 1010,则应计算 10 的两次出现。
$$$^\dagger$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
$$$^\ddagger$$$ 二进制字符串是只包含字符 0 和 1 的字符串。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2500$$$, $$$1 \leq k \leq n$$$) — 所需的好子串的数量和好子串的最大允许长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2500$$$。
输出
对于每个测试用例,输出一个整数 - 二进制字符串 $$$s$$$ 的数量,使得 $$$s$$$ 恰好包含 $$$n$$$ 好子串,并且没有长度严格大于 $$$k$$$ 的好子串。由于该整数可能太大,因此输出它对 $$$998\,244\,353$$$ 取模。
示例
输入 #1
6 1 1 3 2 4 2 5 4 6 2 2450 2391
输出 #1
1 3 5 12 9 259280854
注意
在第一个测试用例中,唯一合适的二进制字符串是 1。字符串 01 不合适,因为它包含长度 $$$2 > 1$$$ 的子字符串 01。
在第二个测试用例中,合适的二进制字符串是 011、110 和 111。
在第三个测试用例中,合适的二进制字符串是 101、0110、0111、1110 和 1111。