VegiCat tiene una cadena $S$ de $n$ letras minúsculas del alfabeto inglés. Quiere construir un diccionario que contenga $k$ subcadenas no vacías distintas de $S$ como sus palabras. Una subcadena es una parte contigua de una cadena. Las subcadenas con el mismo contenido se tratan como la misma palabra, incluso si aparecen en posiciones diferentes de $S$.

Sea $\pi$ una aplicación de las letras $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ a las letras correspondientes en una permutación de las $26$ letras minúsculas del alfabeto inglés. Por ejemplo, la permutación $\texttt{qwertyuiopasdfghjklzxcvbnm}$ define la siguiente aplicación:

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

Para una cadena $u = u_1 u_2 \cdots u_m$, se define

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

Por ejemplo, con la aplicación anterior, $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat quiere que el diccionario contenga una palabra $w$ tal que, tras aplicar cualquier aplicación $\pi$ de este tipo a cada palabra del diccionario, $\pi(w)$ sea siempre la palabra lexicográficamente más pequeña en el diccionario resultante.

Para cada $k = 1, 2, \ldots, n$, halle el número de diccionarios que contienen $k$ palabras distintas y satisfacen el requisito, módulo $998\,244\,353$. Dos diccionarios se consideran diferentes si y solo si contienen conjuntos diferentes de palabras antes de aplicar cualquier aplicación.

Recuerde que la cadena $a$ es lexicográficamente menor que la cadena $b$ si $a$ es un prefijo de $b$ (y $a \neq b$), o si existe un índice $i$ ($1 \le i \le \min(|a|, |b|)$) tal que $a_i < b_i$, y para cualquier índice $j$ ($1 \le j < i$) se cumple $a_j = b_j$.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($1 \le n \le 10^5$).

La segunda línea contiene una cadena $S$ de longitud $n$, formada únicamente por letras minúsculas del alfabeto inglés.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprima $n$ enteros en una línea. El $k$-ésimo entero representa el número de diccionarios que contienen $k$ palabras distintas y satisfacen el requisito, módulo $998\,244\,353$.

Ejemplos

Entrada 1

3
3
aab
4
ppqq
7
abcaabc

Salida 1

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

Nota

Cada diccionario a continuación se escribe como un conjunto de palabras.

Para el primer caso de prueba, $S = \texttt{aab}$, los diccionarios que satisfacen el requisito para $k = 1, 2, 3$ son: