菜貓有一個由 $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}$。

菜貓希望詞典入面包含一個單詞 $w$，令到將任意噉樣嘅映射 $\pi$ 應用落詞典入面嘅每個單詞之後，$\pi(w)$ 喺所得嘅詞典入面永遠都係字典序最細嘅單詞。

對於每個 $k = 1, 2, \ldots, n$，求包含 $k$ 個唔同單詞而且滿足要求嘅詞典數量，對 $998\,244\,353$ 取模。兩本詞典被視為唔同，當且僅當喺應用任何映射之前佢哋包含嘅單詞集合唔同。

重溫一下，字串 $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$。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 10^4$），表示測試用例嘅數量。接落嚟係各個測試用例嘅描述。

每個測試用例嘅第一行包含一個整數 $n$（$1 \le n \le 10^5$）。

第二行包含一個長度為 $n$ 嘅字串 $S$，只由細楷英文字母組成。

保證所有測試用例入面 $n$ 嘅總和唔超過 $10^5$。

輸出格式

對於每個測試用例，喺一行入面輸出 $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

說明

下面每本詞典都寫成一個單詞集合。

對於第一個測試用例 $S = \texttt{aab}$，當 $k = 1, 2, 3$ 時滿足要求嘅詞典如下：