K. Med and Mex
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"I don't know everything, I only know what I know." Let's find out if she knows about permutations that have the same med, mex, and median!

The median of a $$$1$$$-index sorted array $$$a$$$ of length $$$n$$$ is defined in this problem as follows: let $$$x = \frac{n+1}{2}$$$ ($$$x$$$ is not necessarily an integer), then the median is $$$\frac{a_{\lfloor x \rfloor} + a_{\lceil x \rceil} }{2}$$$. The mex of an array is the minimum excluded or the minimum positive integer which is not present.

A nonempty sequence is good if the mex of that sequence and the median of that sequence are equal. Let the value of a good sequence be the mex (and median) of that sequence. There is a permutation $$$p$$$ of all the integers from $$$1$$$ to $$$n$$$. We want to know over all permutations $$$p'$$$ of $$$p$$$ the number subarrays of $$$p'$$$ which are good sequences with value $$$x$$$ for each $$$x$$$ $$$(1 \leq x \leq n)$$$. This is something she knows, but is it something you know?

Input

The first line will contain one integer $$$T$$$, the number of testcases $$$(1 \leq T \leq 5)$$$.

The first line of each testcase contains one integer, $$$n$$$ the length of permutations that are being considered $$$(1 \leq n \leq 10^5)$$$.

 —

Tests in subtasks will be numbered from $$$1 - 20$$$ with samples skipped.

Test $$$i$$$ will satisfy $$$n \leq \min(10^5, 2^i)$$$.

Output

For each testcase, output one line of $$$n$$$ integers where the $$$i$$$-th integer is the number of good sequences with value $$$i$$$ over all permutations of $$$1,2, \dots n$$$. Since these numbers may be very large, please find them modulo $$$998244353$$$.

Example
Input
5
1
2
3
4
15
Output
0 
0 0 
0 4 0 
0 12 0 0 
0 662064978 677633922 778530699 797769592 212803401 839917327 662064978 0 0 0 0 0 0 0
Note

The subarrays which are good subsequences of value $$$2$$$ of the permutation $$$1, 2, 3$$$ are as follows:

$$$[1, 3]$$$ in $$$[1, 3, 2]$$$

$$$[1, 3]$$$ in $$$[2, 1, 3]$$$

$$$[3, 1]$$$ in $$$[2, 3, 1]$$$

$$$[3, 1]$$$ in $$$[3, 1, 2]$$$

 —

Problem Idea: 3366

Problem Preparation: 3366

Occurrences: Novice $$$10$$$, Advanced $$$4$$$