E. Подсчёт бинарных строк
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Патрик называет подстроку$$$^\dagger$$$ бинарной строки$$$^\ddagger$$$ хорошей, если эта подстрока содержит ровно одну 1.

Помогите Патрику посчитать количество бинарных строк $$$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$$$.

Пример
Входные данные
6
1 1
3 2
4 2
5 4
6 2
2450 2391
Выходные данные
1
3
5
12
9
259280854
Примечание

В первом наборе входных данных единственной подходящей бинарной строкой является 1. Строка 01 не подходит, потому что она содержит подстроку 01 длины $$$2 > 1$$$.

Во втором наборе входных данных подходящими бинарными строками являются 011, 110 и 111.

В третьем наборе входных данных подходящими бинарными строками являются 101, 0110, 0111, 1110, 1111.