菜貓有一個由 $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$ 時滿足要求的字典如下：