VegiCatilla on merkkijono $S$, joka koostuu $n$ pienestä englantilaisesta kirjaimesta. Hän haluaa rakentaa sanakirjan, joka sisältää sanoinaan $k$ erilaista epätyhjää merkkijonon $S$ osamerkkijonoa. Osamerkkijono on merkkijonon yhtenäinen osa. Sisällöltään samat osamerkkijonot katsotaan samaksi sanaksi, vaikka ne esiintyisivät eri kohdissa merkkijonossa $S$.

Olkoon $\pi$ kuvaus kirjaimista $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ vastaaviin kirjaimiin $26$ pienen englantilaisen kirjaimen permutaatiossa. Esimerkiksi permutaatio $\texttt{qwertyuiopasdfghjklzxcvbnm}$ määrittelee seuraavan kuvauksen:

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

Merkkijonolle $u = u_1 u_2 \cdots u_m$ määritellään

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

Esimerkiksi yllä olevalla kuvauksella $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat haluaa sanakirjan sisältävän sellaisen sanan $w$, että kun mikä tahansa tällainen kuvaus $\pi$ sovelletaan jokaiseen sanakirjan sanaan, $\pi(w)$ on aina aakkosjärjestyksessä (leksikografisesti) pienin sana tuloksena saadussa sanakirjassa.

Etsi jokaiselle $k = 1, 2, \ldots, n$ sellaisten sanakirjojen lukumäärä modulo $998\,244\,353$, jotka sisältävät $k$ erilaista sanaa ja täyttävät vaatimuksen. Kaksi sanakirjaa katsotaan erilaisiksi, jos ja vain jos ne sisältävät eri sanajoukot ennen minkään kuvauksen soveltamista.

Muistathan, että merkkijono $a$ on leksikografisesti pienempi kuin merkkijono $b$, jos $a$ on merkkijonon $b$ alkuosa (ja $a \neq b$) tai on olemassa indeksi $i$ ($1 \le i \le \min(|a|, |b|)$), jolle $a_i < b_i$, ja kaikilla indekseillä $j$ ($1 \le j < i$) pätee $a_j = b_j$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.

Jokaisen testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$).

Toinen rivi sisältää pituutta $n$ olevan merkkijonon $S$, joka koostuu vain pienistä englantilaisista kirjaimista.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle $n$ kokonaislukua yhdelle riville. $k$:s kokonaisluku ilmaisee sellaisten sanakirjojen lukumäärän modulo $998\,244\,353$, jotka sisältävät $k$ erilaista sanaa ja täyttävät vaatimuksen.

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

Huomautus

Jokainen alla oleva sanakirja on kirjoitettu sanojen joukkona.

Ensimmäisessä testitapauksessa, $S = \texttt{aab}$, vaatimuksen täyttävät sanakirjat arvoilla $k = 1, 2, 3$ ovat: