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

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

18E. Consecutive Run

Constraints

Input

Output

Samples

18E. Consecutive Run

Constraints

Input

Output

Samples