We call a tree with nodes numbered from $$$1$$$ to $$$n$$$ a Manhattan tree only if there exist $$$n$$$ points $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ in a two-dimensional plane such that for any $$$i, j$$$ ($$$1 \leq i \lt j \leq n$$$), the Manhattan distances$$$^*$$$ from $$$(x_i, y_i)$$$ to $$$(x_j, y_j)$$$ is equal to the distance$$$^\dagger$$$ between node $$$i$$$ and node $$$j$$$ in the tree.
Given $$$n$$$, output the number of different$$$^\ddagger$$$ Manhattan trees with nodes numbered from $$$1$$$ to $$$n$$$, modulo $$$998244353$$$.
$$$^*$$$ The Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ in a two-dimensional plane is defined as $$$|x_1 - x_2| + |y_1 - y_2|$$$.
$$$^\dagger$$$ The distance between two nodes $$$i$$$ and $$$j$$$ in a tree is defined as the number of edges in the simple path between node $$$i$$$ and node $$$j$$$.
$$$^\ddagger$$$ We call tree $$$T_1$$$ and tree $$$T_2$$$ different if and only if there's an edge $$$(u, v)$$$ such that $$$(u, v) \in T_1$$$ and $$$(u, v) \notin T_2$$$.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases.
For each test case:
- The only line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^6$$$).
For each test case, output in a new line — the number of different Manhattan trees, modulo $$$998244353$$$.
62367996999999
1 3 1290 16170 412965036 886558470
In the third test case ($$$n=6$$$), for example, the following tree is a Manhattan tree
because there exist $$$6$$$ points $$$(x_1, y_1), (x_2, y_2), \ldots, (x_6, y_6)$$$ in a two-dimensional plane such that for any $$$i, j$$$ ($$$1 \leq i \lt j \leq 6$$$), the Manhattan distance from $$$(x_i, y_i)$$$ to $$$(x_j, y_j)$$$ is equal to the distance between node $$$i$$$ and node $$$j$$$ in the tree.
An example of the possible 6 points. However, the following tree is not a Manhattan tree.
