VegiCat は $n$ 個の英小文字からなる文字列 $S$ を持っています。彼は $S$ の相異なる $k$ 個の空でない部分文字列を単語として含む辞書を作りたいと考えています。部分文字列とは、文字列の連続する一部分のことです。内容が同じ部分文字列は、たとえ $S$ 内の異なる位置に現れても同じ単語として扱われます。

$\pi$ を文字 $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ から $26$ 個の英小文字の順列における対応する文字への写像とします。例えば、順列 $\texttt{qwertyuiopasdfghjklzxcvbnm}$ は次の写像を定めます：

$$ \begin{array}{c|cccccccccccccccccccccccccc} c & \texttt{a} & \texttt{b} & \texttt{c} & \texttt{d} & \texttt{e} & \texttt{f} & \texttt{g} & \texttt{h} & \texttt{i} & \texttt{j} & \texttt{k} & \texttt{l} & \texttt{m} & \texttt{n} & \texttt{o} & \texttt{p} & \texttt{q} & \texttt{r} & \texttt{s} & \texttt{t} & \texttt{u} & \texttt{v} & \texttt{w} & \texttt{x} & \texttt{y} & \texttt{z} \\ \hline \pi(c) & \texttt{q} & \texttt{w} & \texttt{e} & \texttt{r} & \texttt{t} & \texttt{y} & \texttt{u} & \texttt{i} & \texttt{o} & \texttt{p} & \texttt{a} & \texttt{s} & \texttt{d} & \texttt{f} & \texttt{g} & \texttt{h} & \texttt{j} & \texttt{k} & \texttt{l} & \texttt{z} & \texttt{x} & \texttt{c} & \texttt{v} & \texttt{b} & \texttt{n} & \texttt{m} \end{array} $$

文字列 $u = u_1 u_2 \cdots u_m$ に対して、次のように定義します：

$$ \pi(u) = \pi(u_1)\pi(u_2) \cdots \pi(u_m). $$

例えば、上の写像のもとでは $\pi(\texttt{apple}) = \texttt{qhhst}$ です。

VegiCat は、どのような写像 $\pi$ を辞書内のすべての単語に適用しても、得られる辞書の中で $\pi(w)$ が常に辞書順で最小の単語となるような単語 $w$ が辞書に含まれているようにしたいと考えています。

各 $k = 1, 2, \ldots, n$ について、相異なる $k$ 個の単語を含み条件を満たす辞書の個数を $998\,244\,353$ で割った余りを求めてください。2つの辞書は、写像を適用する前の単語の集合が異なるとき、かつそのときに限り異なるとみなされます。

なお、文字列 $a$ が文字列 $b$ より辞書順で小さいとは、$a$ が $b$ の接頭辞である（かつ $a \neq b$）、またはある添字 $i$（$1 \le i \le \min(|a|, |b|)$）が存在して $a_i < b_i$ かつ任意の添字 $j$（$1 \le j < i$）に対して $a_j = b_j$ が成り立つことをいいます。

入力

1行目にはテストケースの個数を表す整数 $T$（$1 \le T \le 10^4$）が与えられます。続いて各テストケースが与えられます。

各テストケースの1行目には整数 $n$（$1 \le n \le 10^5$）が与えられます。

2行目には英小文字のみからなる長さ $n$ の文字列 $S$ が与えられます。

すべてのテストケースにおける $n$ の総和は $10^5$ 以下であることが保証されます。

出力

各テストケースについて、1行に $n$ 個の整数を出力してください。$k$ 番目の整数は、相異なる $k$ 個の単語を含み条件を満たす辞書の個数を $998\,244\,353$ で割った余りを表します。

入出力例

入力 1

3
3
aab
4
ppqq
7
abcaabc

出力 1

5 4 3
8 10 11 10
21 52 87 119 139 128 84

注記

以下では、各辞書を単語の集合として表記します。

1番目のテストケース $S = \texttt{aab}$ において、$k = 1, 2, 3$ に対して条件を満たす辞書は次の通りです：