VegiCat har en streng $S$ bestående av $n$ små engelske bokstaver. Han ønsker å bygge en ordbok som inneholder $k$ forskjellige ikke-tomme delstrenger av $S$ som ord. En delstreng er en sammenhengende del av en streng. Delstrenger med samme innhold behandles som samme ord, selv om de forekommer på ulike posisjoner i $S$.

La $\pi$ være en avbildning fra bokstavene $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ til de tilsvarende bokstavene i en permutasjon av de $26$ små engelske bokstavene. For eksempel definerer permutasjonen $\texttt{qwertyuiopasdfghjklzxcvbnm}$ følgende avbildning:

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

For en streng $u = u_1 u_2 \cdots u_m$, definer

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

Med avbildningen ovenfor er for eksempel $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat ønsker at ordboken skal inneholde et ord $w$ slik at etter å ha brukt en hvilken som helst slik avbildning $\pi$ på hvert ord i ordboken, er $\pi(w)$ alltid det leksikografisk minste ordet i den resulterende ordboken.

For hver $k = 1, 2, \ldots, n$, finn antall ordbøker som inneholder $k$ forskjellige ord og oppfyller kravet, modulo $998\,244\,353$. To ordbøker regnes som forskjellige hvis og bare hvis de inneholder ulike mengder av ord før noen avbildning brukes.

Husk at strengen $a$ er leksikografisk mindre enn strengen $b$ hvis $a$ er et prefiks av $b$ (og $a \neq b$), eller det finnes en indeks $i$ ($1 \le i \le \min(|a|, |b|)$) slik at $a_i < b_i$, og for enhver indeks $j$ ($1 \le j < i$) gjelder $a_j = b_j$.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder et heltall $n$ ($1 \le n \le 10^5$).

Den andre linjen inneholder en streng $S$ med lengde $n$, som kun består av små engelske bokstaver.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle, skriv ut $n$ heltall på én linje. Det $k$-te heltallet representerer antall ordbøker som inneholder $k$ forskjellige ord og oppfyller kravet, 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

Merk

Hver ordbok nedenfor er skrevet som en mengde med ord.

For det første testtilfellet, $S = \texttt{aab}$, er ordbøkene som oppfyller kravet for $k = 1, 2, 3$: