VegiCat á streng $S$ úr $n$ enskum lágstöfum. Hann vill búa til orðabók sem inniheldur $k$ ólíka, ótóma hlutstrengi úr $S$ sem orð. Hlutstrengur er samfelldur hluti strengs. Hlutstrengir með sama innihaldi eru meðhöndlaðir sem sama orðið, jafnvel þótt þeir komi fyrir á ólíkum stöðum í $S$.

Látum $\pi$ vera vörpun frá bókstöfunum $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ yfir í samsvarandi bókstafi í umröðun á ensku lágstöfunum $26$. Til dæmis skilgreinir umröðunin $\texttt{qwertyuiopasdfghjklzxcvbnm}$ eftirfarandi vörpun:

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

Fyrir streng $u = u_1 u_2 \cdots u_m$ skilgreinum við

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

Til dæmis, með vörpuninni hér að ofan, er $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat vill að orðabókin innihaldi orð $w$ þannig að eftir að hvaða slíkri vörpun $\pi$ sem er hefur verið beitt á hvert orð í orðabókinni sé $\pi(w)$ alltaf minnsta orðið í stafrófsröð (lexíkógrafískt) í orðabókinni sem fæst.

Fyrir hvert $k = 1, 2, \ldots, n$, finnið fjölda orðabóka sem innihalda $k$ ólík orð og uppfylla skilyrðið, modulo $998\,244\,353$. Tvær orðabækur teljast ólíkar ef og aðeins ef þær innihalda ólík mengi orða áður en nokkurri vörpun er beitt.

Rifjum upp að strengur $a$ er lexíkógrafískt minni en strengur $b$ ef $a$ er forskeyti í $b$ (og $a \neq b$), eða ef til er vísir $i$ ($1 \le i \le \min(|a|, |b|)$) þannig að $a_i < b_i$, og fyrir hvern vísi $j$ ($1 \le j < i$) gildir $a_j = b_j$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir.

Fyrsta línan í hverju prófunartilviki inniheldur heiltölu $n$ ($1 \le n \le 10^5$).

Önnur línan inniheldur streng $S$ af lengd $n$, sem samanstendur eingöngu af enskum lágstöfum.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta $n$ heiltölur á einni línu. $k$-ta heiltalan táknar fjölda orðabóka sem innihalda $k$ ólík orð og uppfylla skilyrðið, 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

Athugasemd

Hver orðabók hér að neðan er skrifuð sem mengi orða.

Fyrir fyrsta prófunartilvikið, $S = \texttt{aab}$, eru orðabækurnar sem uppfylla skilyrðið fyrir $k = 1, 2, 3$: