色 $1$、色 $2$、…、色 $N$ の $N$ 個のボールがこの順に一列に並んでおり、先頭は色 $1$ のボールです。
これから、以下の一連の操作を $K$ 回行います。

• 先頭のボールを列から取り出して、このボールに $1$ つ穴をあける。
• 残ったボールの列の先頭か末尾、もしくはあるボールとボールの間の合計 $N$ 箇所から一様ランダムに場所を選び、取り出したボールを挿入する。

$K$ 回の操作の後、色 $i\ (1\leq i\leq N)$ のボールにあいた穴の個数の期待値をそれぞれ $\text{mod }998244353$ で求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

すべてのテストケースについて、以下の制約を満たす。

• 入力はすべて整数
• $1\leq T\leq 10^4$
• $2\leq N\leq 2\times 10^5$
• $1\leq K\leq 10^{18}$
• $1$ つの入力における $N$ の総和は $2\times 10^5$ を超えない。

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($200$ 点)

• $N \leq 100$
• $1$ つの入力における $N^3$ の総和は $10^6$ を超えない。

2. ($300$ 点)

• $N \leq 2000$
• $1$ つの入力における $N^2$ の総和は $4\times 10^6$ を超えない。

3. ($500$ 点)

• 追加の制約はない。

入力は以下の形式で標準入力から与えられる。

$\mathrm{case}_i$ は $i$ 番目のテストケースを表す。 各テストケースは以下の形式で与えられる。

$T$ 行出力せよ。
$i$ 行目 $(1\leq i\leq T)$ には、$i$ 個目のテストケースに対する色 $1$、色 $2$、…、色 $N$ についての答えを、順に空白区切りで出力せよ。