VegiCat har en sträng $S$ med $n$ små engelska bokstäver. Han vill bygga en ordbok som innehåller $k$ olika icke-tomma delsträngar av $S$ som sina ord. En delsträng är en sammanhängande del av en sträng. Delsträngar med samma innehåll behandlas som samma ord, även om de förekommer på olika positioner i $S$.

Låt $\pi$ vara en avbildning från bokstäverna $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ till motsvarande bokstäver i en permutation av de $26$ små engelska bokstäverna. Till exempel definierar permutationen $\texttt{qwertyuiopasdfghjklzxcvbnm}$ följande 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} $$

För en sträng $u = u_1 u_2 \cdots u_m$, definiera

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

Med avbildningen ovan gäller till exempel $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat vill att ordboken ska innehålla ett ord $w$ sådant att efter att en godtycklig sådan avbildning $\pi$ har tillämpats på varje ord i ordboken, är $\pi(w)$ alltid det lexikografiskt minsta ordet i den resulterande ordboken.

För varje $k = 1, 2, \ldots, n$, bestäm antalet ordböcker som innehåller $k$ olika ord och uppfyller kravet, modulo $998\,244\,353$. Två ordböcker betraktas som olika om och endast om de innehåller olika mängder av ord innan någon avbildning tillämpas.

Kom ihåg att strängen $a$ är lexikografiskt mindre än strängen $b$ om $a$ är ett prefix till $b$ (och $a \neq b$), eller om det finns ett index $i$ ($1 \le i \le \min(|a|, |b|)$) sådant att $a_i < b_i$, och för varje index $j$ ($1 \le j < i$) gäller $a_j = b_j$.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^4$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller ett heltal $n$ ($1 \le n \le 10^5$).

Den andra raden innehåller en sträng $S$ med längden $n$, som endast består av små engelska bokstäver.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut $n$ heltal på en rad. Det $k$-te heltalet representerar antalet ordböcker som innehåller $k$ olika ord och uppfyller 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

Anmärkning

Varje ordbok nedan skrivs som en mängd av ord.

För det första testfallet, $S = \texttt{aab}$, är de ordböcker som uppfyller kravet för $k = 1, 2, 3$: