E. Фермерская игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фермер Нхой привел своих коров на ферму Фермера Джона, чтобы поиграть в игру! Ферма Фермера Джона может быть представлена в виде числовой прямой со стенами в точках $$$0$$$ и $$$l + 1$$$. На ферме есть $$$2n$$$ коров, причем $$$n$$$ коров принадлежат Фермеру Джону, а остальные $$$n$$$ — Фермеру Нхою. Они размещают своих коров в различных точках так, чтобы никакие две коровы одного фермера не были соседними. Две коровы являются соседними, если между ними нет других коров.

Формально, если $$$a_1, a_2, \ldots, a_n$$$ представляют позиции коров фермера Джона, а $$$b_1, b_2, \ldots, b_n$$$ представляют позиции коров фермера Нхоя, то $$$0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n < l + 1$$$, или $$$0 < b_1 < a_1 < b_2 < a_2 < \ldots < b_n < a_n < l + 1$$$.

За один ход фермер выбирает число $$$k$$$ $$$(1 \leq k \leq n)$$$ и направление (влево или вправо). Затем этот фермер выбирает $$$k$$$ своих коров и перемещает их на одну позицию в выбранном направлении. Фермер не может переместить ни одну из своих коров на стены или на корову другого фермера. Если фермер не может переместить ни одной коровы, то он проигрывает. Фермер Джон начинает игру и делает первый ход.

Учитывая $$$l$$$ и $$$n$$$, найдите количество возможных конфигураций игры, при которых Фермер Джон выиграет, если оба фермера играют оптимально. В случае, если при оптимальной игре она продолжается бесконечно долго, считается, что никто из фермеров не выигрывает. Конфигурация отличается от другой, если существует такое $$$i$$$, что $$$a_i$$$ или $$$b_i$$$ отличаются. Выведите ответ по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Каждый набор входных данных содержит два целых числа $$$l$$$ и $$$n$$$ ($$$2 \leq l \leq 10^6, 1 \leq n \leq \lfloor \frac{l}{2} \rfloor$$$) — длина числовой прямой и количество коров, которое поставит каждый фермер.

Гарантируется, что сумма $$$l$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
3
2 1
3 1
420 69
Выходные данные
0
2
870279412
Примечание

Пусть J обозначает корову Фермера Джона, N обозначает корову Фермера Нхоя, а _ обозначает пустое место.

Для первого набора входных данных возможны две конфигурации: JN или NJ. В обоих случаях, поскольку Фермер Джон делает первый ход и не может сделать ни одного хода, он не может выиграть.

Во втором случае есть две возможные конфигурации для победы Фермера Джона: N_J и J_N.