問題文

正整数 $N$ と、$(1, 2, \dots , N)$ の順列 $P = (P_{1}, P_{2}, \dots, P_{N})$ が与えられます。

$k = 1, 2, \dots, N$ について、以下の問いに答えてください。

• $P$ をちょうど $k$ 個の非空な連続部分列に分解し、並び替えた後に連結することでできる $(1, 2, \dots, N)$ の順列であって、辞書順最小のもののローリングハッシュを求めてください。

ただし、正整数列 $a = (a_{1}, a_{2}, \dots, a_{n})$ のローリングハッシュは $\displaystyle\sum_{i = 1}^{n}a_{i}\cdot 10^{n - i}\pmod{998244353}$ と定義します。

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

制約

• $1\leq T\leq 2\times 10^{5}$
• $1\leq N\leq 2\times 10^{5}$
• $P$ は $(1, 2, \dots, N)$ の順列
• $T$ 個のテストケースに渡る $N$ の総和は $2\times 10^{5}$ 以下
• 入力は全て整数

入力

$T$
$case_{1}$
$case_{2}$
$\vdots$
$case_{T}$

ここで、$case_{i}$ は $i$ 番目のテストケースを表し、以下の形式で与えられます。

$N$
$P_{1}$ $P_{2}$ $\dots$ $P_{N}$

出力

$T$ 行出力してください。

$i$ 行目には $i$ 番目のテストケースの $k = 1, 2, \dots, N$ に対する答えを、この順に空白区切りで出力してください。

サンプル

4
3
3 1 2
4
4 2 1 3
5
2 5 1 4 3
8
5 8 1 7 6 2 4 3

312 123 123
4213 1342 1324 1234
25143 14325 12543 12435 12345
58176243 17624358 15876243 12435876 12435768 12345876 12345768 12345678