E. 2...3...4.... Замечательно! Замечательно!
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Стека есть массив $$$a$$$ длины $$$n$$$ такой, что $$$a_i = i$$$ для всех $$$i$$$ ($$$1 \leq i \leq n$$$). Он выберет целое положительное число $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$) и выполнит следующую операцию над $$$a$$$ любое число раз (возможно, $$$0$$$):

  • Выбрать из $$$a$$$ подпоследовательность$$$^\dagger$$$ $$$s$$$ длины $$$2 \cdot k + 1$$$. Далее, удалить первые $$$k$$$ элементов $$$s$$$ из $$$a$$$. Чтобы все было идеально сбалансировано (как и должно быть), также удалить последние $$$k$$$ элементов $$$s$$$ из $$$a$$$.

Стеку стало интересно, сколько массивов $$$a$$$ он может получить в итоге для каждого $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$). Поскольку Стек плохо справляется с математическими задачами, ему нужна ваша помощь.

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

$$$^\dagger$$$ Последовательность $$$x$$$ является подпоследовательностью $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов. Например, $$$[1, 3]$$$, $$$[1, 2, 3]$$$ и $$$[2, 3]$$$ являются подпоследовательностями $$$[1, 2, 3]$$$. С другой стороны, $$$[3, 1]$$$ и $$$[2, 1, 3]$$$ не являются подпоследовательностями $$$[1, 2, 3]$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 10^6$$$) — длину массива $$$a$$$.

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

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

Для каждого набора входных данных в отдельной строке выведите $$$\lfloor \frac{n-1}{2} \rfloor$$$ целых чисел, разделенных пробелами, где $$$i$$$-е число равняется количеству (по модулю $$$998\,244\,353$$$) массивов, которые Стек может получить, если выберет $$$k=i$$$.

Пример
Входные данные
4
3
4
5
10
Выходные данные
2 
4 
10 2 
487 162 85 10
Примечание

В первом наборе входных данных для $$$k=1$$$ возможны два $$$a$$$:

  • $$$[1,2,3]$$$;
  • $$$[2]$$$.

Во втором наборе входных данных для $$$k=1$$$ возможны четыре $$$a$$$:

  • $$$[1,2,3,4]$$$;
  • $$$[1,3]$$$;
  • $$$[2,3]$$$;
  • $$$[2,4]$$$.

В третьем наборе входных данных для $$$k=2$$$ возможны два $$$a$$$:

  • $$$[1,2,3,4,5]$$$;
  • $$$[3]$$$.