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

Вам даны два целых числа $$$n$$$ и $$$m$$$.

Массив $$$a$$$ длины $$$n$$$ называется хорошим, если он удовлетворяет следующим двум условиям:

  • $$$\color{red}{m + 2} \ge a_1 \ge a_2 \ge \ldots \ge a_{n-1} \ge a_n \ge 1$$$;
  • $$$(a_1 \bmod a_2) + (a_2 \bmod a_3) + \ldots + (a_{n-1} \bmod a_n) = m$$$.

Ваша задача — найти количество хороших массивов. Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2\,000$$$) — количество наборов входных данных. Далее следует описание наборов.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 4\,000$$$; $$$1 \le m \le 4\,000$$$), разделённых пробелом.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$4000$$$, а сумма $$$m$$$ по всем наборам входных данных не превосходит $$$4000$$$.

Выходные данные

Для каждого набора входных данных выведите количество хороших массивов. Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

Пример
Входные данные
6
3 1
3 2
6 7
41 67
998 244
353 420
Выходные данные
3
1
60
972763487
288208692
566410295
Примечание

В первом наборе входных данных хорошими являются следующие массивы:

  • $$$[3, 2, 1]$$$: $$$(3 \bmod 2) + (2 \bmod 1) = 1 + 0 = 1$$$.
  • $$$[3, 2, 2]$$$: $$$(3 \bmod 2) + (2 \bmod 2) = 1 + 0 = 1$$$.
  • $$$[3, 3, 2]$$$: $$$(3 \bmod 3) + (3 \bmod 2) = 0 + 1 = 1$$$.

Во втором наборе входных данных единственным хорошим массивом является $$$[4, 3, 2]$$$.