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

У Shohag есть массив целых чисел $$$a$$$. Изначально $$$a = [0, 1]$$$. Он может выполнять следующую операцию любое количество раз:

  • Пусть $$$k$$$ — количество инверсий$$$^{\text{∗}}$$$ в текущем массиве $$$a$$$.
  • Вставить $$$k$$$ на любую позицию в $$$a$$$, в том числе возможно в начало или конец.

Например, если $$$a = [4, 6, 2, 4]$$$, то количество инверсий равно $$$k = 3$$$. Таким образом, после операции вы можете получить следующие массивы: $$$[\textbf{3}, 4, 6, 2, 4]$$$, $$$[4, \textbf{3}, 6, 2, 4]$$$, $$$[4, 6, \textbf{3}, 2, 4]$$$, $$$[4, 6, 2, \textbf{3}, 4]$$$, и $$$[4, 6, 2, 4, \textbf{3}]$$$.

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

$$$^{\text{∗}}$$$Количество инверсий в массиве $$$a$$$ — это количество пар индексов ($$$i$$$, $$$j$$$) таких, что $$$i < j$$$ и $$$a_i > a_j$$$.

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

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

Первая и единственная строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 10^6$$$).

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

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

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

Пример
Входные данные
4
4
2
7
69
Выходные данные
5
1
682
325188814
Примечание

В первом наборе входных данных можно получить следующие $$$5$$$ массивов (вставленное количество инверсий выделено жирным шрифтом):

  • $$$[0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, 1, \textbf{0}]$$$,
  • $$$[0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, \textbf{0}, 1]$$$,
  • $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, 0, \textbf{1}]$$$,
  • $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, \textbf{1}, 0]$$$,
  • $$$[0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [\textbf{1}, 0, 1, 0]$$$.