311074: CF1930E. 2..3...4.... Wonderful! Wonderful!

E. 2..3...4.... Wonderful! Wonderful!time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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]$.

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$.

ExampleInput

4
3
4
5
10

Output

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]$.

题目大意：
题目描述了一个数组操作游戏。给定一个长度为n的数组a，其中的元素a_i等于i（对于所有i，1≤i≤n）。游戏者将选择一个正整数k（1≤k≤⌊(n-1)/2⌋），并对数组a进行任意次数（可能为0次）的以下操作：
- 从数组a中选择一个长度为2×k+1的子序列s。然后，从a中删除s的前k个元素。为了保持完美平衡，他还会从a中删除s的后k个元素。

游戏者想要知道对于每个k（1≤k≤⌊(n-1)/2⌋），他最终可以得到多少个不同的数组a。由于可能的数组数量可能非常大，请将结果模998,244,353后输出。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤2×10^3），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（3≤n≤10^6），表示数组a的长度。
- 保证所有测试用例的n之和不超过10^6。

输出：
- 对于每个测试用例，输出一行，包含⌊(n-1)/2⌋个整数，第i个数表示游戏者选择k=i时可以得到的不同数组a的数量模998,244,353。

示例：
输入：
```
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]。题目大意： 题目描述了一个数组操作游戏。给定一个长度为n的数组a，其中的元素a_i等于i（对于所有i，1≤i≤n）。游戏者将选择一个正整数k（1≤k≤⌊(n-1)/2⌋），并对数组a进行任意次数（可能为0次）的以下操作： - 从数组a中选择一个长度为2×k+1的子序列s。然后，从a中删除s的前k个元素。为了保持完美平衡，他还会从a中删除s的后k个元素。 游戏者想要知道对于每个k（1≤k≤⌊(n-1)/2⌋），他最终可以得到多少个不同的数组a。由于可能的数组数量可能非常大，请将结果模998,244,353后输出。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤2×10^3），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（3≤n≤10^6），表示数组a的长度。 - 保证所有测试用例的n之和不超过10^6。 输出： - 对于每个测试用例，输出一行，包含⌊(n-1)/2⌋个整数，第i个数表示游戏者选择k=i时可以得到的不同数组a的数量模998,244,353。 示例： 输入： ``` 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]。