VegiCat ha una stringa $S$ di $n$ lettere minuscole dell'alfabeto inglese. Vuole costruire un dizionario che contenga $k$ sottostringhe non vuote distinte di $S$ come parole. Una sottostringa è una parte contigua di una stringa. Le sottostringhe con lo stesso contenuto sono considerate come la stessa parola, anche se compaiono in posizioni diverse in $S$.

Sia $\pi$ una mappa dalle lettere $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ alle lettere corrispondenti in una permutazione delle $26$ lettere minuscole dell'alfabeto inglese. Ad esempio, la permutazione $\texttt{qwertyuiopasdfghjklzxcvbnm}$ definisce la seguente mappa:

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

Per una stringa $u = u_1 u_2 \cdots u_m$, definiamo

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

Ad esempio, con la mappa precedente, $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat vuole che il dizionario contenga una parola $w$ tale che, dopo aver applicato una qualsiasi mappa $\pi$ di questo tipo a ogni parola del dizionario, $\pi(w)$ sia sempre la parola lessicograficamente più piccola nel dizionario risultante.

Per ogni $k = 1, 2, \ldots, n$, trova il numero di dizionari che contengono $k$ parole distinte e soddisfano il requisito, modulo $998\,244\,353$. Due dizionari sono considerati diversi se e solo se contengono insiemi diversi di parole prima che venga applicata qualsiasi mappa.

Ricorda che la stringa $a$ è lessicograficamente minore della stringa $b$ se $a$ è un prefisso di $b$ (e $a \neq b$), oppure se esiste un indice $i$ ($1 \le i \le \min(|a|, |b|)$) tale che $a_i < b_i$, e per ogni indice $j$ ($1 \le j < i$) vale $a_j = b_j$.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di prova. Segue la descrizione dei casi di prova.

La prima riga di ogni caso di prova contiene un intero $n$ ($1 \le n \le 10^5$).

La seconda riga contiene una stringa $S$ di lunghezza $n$, composta esclusivamente da lettere minuscole dell'alfabeto inglese.

È garantito che la somma di $n$ su tutti i casi di prova non superi $10^5$.

Output

Per ogni caso di prova, stampa $n$ interi su una riga. Il $k$-esimo intero rappresenta il numero di dizionari che contengono $k$ parole distinte e soddisfano il requisito, modulo $998\,244\,353$.

Examples

Input 1

3
3
aab
4
ppqq
7
abcaabc

Output 1

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

Note

Ogni dizionario qui sotto è scritto come un insieme di parole.

Per il primo caso di prova, $S = \texttt{aab}$, i dizionari che soddisfano il requisito per $k = 1, 2, 3$ sono: