VegiCat ma napis $S$ składający się z $n$ małych liter alfabetu angielskiego. Chce zbudować słownik zawierający jako słowa $k$ różnych niepustych podsłów napisu $S$. Podsłowo to spójny fragment napisu. Podsłowa o tej samej zawartości są traktowane jako to samo słowo, nawet jeśli występują na różnych pozycjach w $S$.

Niech $\pi$ będzie odwzorowaniem przyporządkowującym literom $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ odpowiednie litery pewnej permutacji $26$ małych liter alfabetu angielskiego. Na przykład permutacja $\texttt{qwertyuiopasdfghjklzxcvbnm}$ definiuje następujące odwzorowanie:

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

Dla napisu $u = u_1 u_2 \cdots u_m$ definiujemy

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

Na przykład dla powyższego odwzorowania mamy $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat chce, aby słownik zawierał takie słowo $w$, że po zastosowaniu dowolnego takiego odwzorowania $\pi$ do każdego słowa w słowniku, $\pi(w)$ jest zawsze leksykograficznie najmniejszym słowem w otrzymanym słowniku.

Dla każdego $k = 1, 2, \ldots, n$ wyznacz liczbę słowników zawierających $k$ różnych słów i spełniających warunek zadania, modulo $998\,244\,353$. Dwa słowniki uznajemy za różne wtedy i tylko wtedy, gdy przed zastosowaniem jakiegokolwiek odwzorowania zawierają różne zbiory słów.

Przypomnijmy, że napis $a$ jest leksykograficznie mniejszy od napisu $b$, jeśli $a$ jest prefiksem $b$ (oraz $a \neq b$) lub istnieje taki indeks $i$ ($1 \le i \le \min(|a|, |b|)$), że $a_i < b_i$ oraz dla każdego indeksu $j$ ($1 \le j < i$) zachodzi $a_j = b_j$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Poniżej znajdują się opisy kolejnych przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera liczbę całkowitą $n$ ($1 \le n \le 10^5$).

Drugi wiersz zawiera napis $S$ o długości $n$, składający się wyłącznie z małych liter alfabetu angielskiego.

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu $n$ liczb całkowitych. $k$-ta liczba całkowita oznacza liczbę słowników zawierających $k$ różnych słów i spełniających warunek zadania, modulo $998\,244\,353$.

Przykład

Wejście 1

3
3
aab
4
ppqq
7
abcaabc

Wyjście 1

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

Uwagi

Każdy słownik poniżej zapisano jako zbiór słów.

Dla pierwszego przypadku testowego, $S = \texttt{aab}$, słownikami spełniającymi warunek dla $k = 1, 2, 3$ są: