VegiCat possède une chaîne de caractères $S$ composée de $n$ lettres minuscules de l'alphabet anglais. Il souhaite construire un dictionnaire contenant $k$ sous-chaînes non vides distinctes de $S$ en tant que mots. Une sous-chaîne est une partie contiguë d'une chaîne. Les sous-chaînes ayant le même contenu sont considérées comme le même mot, même si elles apparaissent à des positions différentes dans $S$.

Soit $\pi$ une application associant aux lettres $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ les lettres correspondantes dans une permutation des $26$ lettres minuscules de l'alphabet anglais. Par exemple, la permutation $\texttt{qwertyuiopasdfghjklzxcvbnm}$ définit l'application suivante :

$$ \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} $$

Pour une chaîne $u = u_1 u_2 \cdots u_m$, on définit

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

Par exemple, avec l'application ci-dessus, $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat souhaite que le dictionnaire contienne un mot $w$ tel qu'après avoir appliqué n'importe quelle application $\pi$ de ce type à chaque mot du dictionnaire, $\pi(w)$ soit toujours le mot lexicographiquement le plus petit du dictionnaire résultant.

Pour chaque $k = 1, 2, \ldots, n$, trouvez le nombre de dictionnaires contenant $k$ mots distincts qui satisfont cette condition, modulo $998\,244\,353$. Deux dictionnaires sont considérés comme différents si et seulement s'ils contiennent des ensembles de mots différents avant l'application de toute bijection.

Rappelons qu'une chaîne $a$ est lexicographiquement plus petite qu'une chaîne $b$ si $a$ est un préfixe de $b$ (et $a \neq b$), ou s'il existe un indice $i$ ($1 \le i \le \min(|a|, |b|)$) tel que $a_i < b_i$ et que pour tout indice $j$ ($1 \le j < i$), $a_j = b_j$.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier $n$ ($1 \le n \le 10^5$).

La deuxième ligne contient une chaîne $S$ de longueur $n$, composée uniquement de lettres minuscules de l'alphabet anglais.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez $n$ entiers sur une seule ligne. Le $k$-ième entier représente le nombre de dictionnaires contenant $k$ mots distincts et satisfaisant la condition, modulo $998\,244\,353$.

Exemples

Entrée 1

3
3
aab
4
ppqq
7
abcaabc

Sortie 1

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

Remarque

Chaque dictionnaire ci-dessous est écrit sous la forme d'un ensemble de mots.

Pour le premier cas de test, $S = \texttt{aab}$, les dictionnaires qui satisfont la condition pour $k = 1, 2, 3$ sont :