#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/18/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Consecutive Run - Repovive Standard Round 6 | Repovive

18E. Consecutive Run

2500 pts2s256 MB

You are given an integer $n$ .

Consider a permutation $p_1,p_2,\ldots,p_n$ of $1,2,\ldots,n$ .

A contiguous segment $p_l,p_{l+1},\ldots,p_r$ is called consecutive increasing if $p_{l+i}=p_l+i$ for every $0\le i\le r-l$ .

The value of a permutation is the maximum length of a consecutive increasing segment in it.

For every $k$ from $1$ to $n$ , find the number of permutations of value exactly $k$ . Output each answer modulo $998244353$ .

Constraints

$1 \le t \le 100$
$1 \le n \le 2000$
The sum of $n$ over all test cases is at most $2000$

Input

t

\left. \begin{array}{l} n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_n \end{array} \right\} \times t

Here, $ans_k$ is the number of permutations whose value is exactly $k$ , taken modulo $998244353$ .

Samples

Input

Case 1

Case 2

Case 3

Case 4

Explanation

Case 1

The only permutation is $(1)$ , and its value is $1$ .

Case 2

The permutations $(2,1)$ and $(1,2)$ have values $1$ and $2$ , respectively.

Case 3

Among the six permutations, three have value $1$ , two have value $2$ , and only $(1,2,3)$ has value $3$ .

Case 4

For example, $(1,2,5,3,4)$ has value $2$ . Only $(1,2,3,4,5)$ has value $5$ .

Output

Case 1

Case 2

1 1

Case 3

3 2 1

Case 4

53 53 11 2 1

You are given an integer $n$ .

Consider a permutation $p_1,p_2,\ldots,p_n$ of $1,2,\ldots,n$ .

A contiguous segment $p_l,p_{l+1},\ldots,p_r$ is called consecutive increasing if $p_{l+i}=p_l+i$ for every $0\le i\le r-l$ .

The value of a permutation is the maximum length of a consecutive increasing segment in it.

For every $k$ from $1$ to $n$ , find the number of permutations of value exactly $k$ . Output each answer modulo $998244353$ .

$1 \le t \le 100$
$1 \le n \le 2000$
The sum of $n$ over all test cases is at most $2000$

t

\left. \begin{array}{l} n \end{array} \right\} \times t

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_n \end{array} \right\} \times t

Here, $ans_k$ is the number of permutations whose value is exactly $k$ , taken modulo $998244353$ .

The only permutation is $(1)$ , and its value is $1$ .

The permutations $(2,1)$ and $(1,2)$ have values $1$ and $2$ , respectively.

Among the six permutations, three have value $1$ , two have value $2$ , and only $(1,2,3)$ has value $3$ .

For example, $(1,2,5,3,4)$ has value $2$ . Only $(1,2,3,4,5)$ has value $5$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

18E. Consecutive Run

Constraints

Input

Output

Samples

18E. Consecutive Run

Constraints

Input

Output

Samples