2..3...4...
Description
Stack has an array $a$ of length $n$ such that $a_i = i$ for all $i$ ($1 \leq i \leq n$). He will select a positive integer $k$ ($1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$) and do the following operation on $a$ any number (possibly $0$) of times.
- Select a subsequence$^\dagger$ $s$ of length $2 \cdot k + 1$ from $a$. Now, he will delete the first $k$ elements of $s$ from $a$. To keep things perfectly balanced (as all things should be), he will also delete the last $k$ elements of $s$ from $a$.
Stack wonders how many arrays $a$ can he end up with for each $k$ ($1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$). As Stack is weak at counting problems, he needs your help.
Since the number of arrays might be too large, please print it modulo $998\,244\,353$.
$^\dagger$ A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by deleting several (possibly, zero or all) elements. For example, $[1, 3]$, $[1, 2, 3]$ and $[2, 3]$ are subsequences of $[1, 2, 3]$. On the other hand, $[3, 1]$ and $[2, 1, 3]$ are not subsequences of $[1, 2, 3]$.
Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^3$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($3 \leq n \leq 10^6$) — the length of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
For each test, on a new line, print $\lfloor \frac{n-1}{2} \rfloor$ space-separated integers — the $i$-th integer representing the number of arrays modulo $998\,244\,353$ that Stack can get if he selects $k=i$.
Input
Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^3$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($3 \leq n \leq 10^6$) — the length of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
Output
For each test, on a new line, print $\lfloor \frac{n-1}{2} \rfloor$ space-separated integers — the $i$-th integer representing the number of arrays modulo $998\,244\,353$ that Stack can get if he selects $k=i$.
4
3
4
5
10
2
4
10 2
487 162 85 10
Note
In the first test case, two $a$ are possible for $k=1$:
- $[1,2,3]$;
- $[2]$.
In the second test case, four $a$ are possible for $k=1$:
- $[1,2,3,4]$;
- $[1,3]$;
- $[2,3]$;
- $[2,4]$.
In the third test case, two $a$ are possible for $k=2$:
- $[1,2,3,4,5]$;
- $[3]$.