VegiCat hat eine Zeichenkette $S$ aus $n$ englischen Kleinbuchstaben. Er möchte ein Wörterbuch erstellen, das $k$ verschiedene nichtleere Teilstrings von $S$ als Wörter enthält. Ein Teilstring ist ein zusammenhängender Teil einer Zeichenkette. Teilstrings mit demselben Inhalt werden als dasselbe Wort betrachtet, selbst wenn sie an unterschiedlichen Positionen in $S$ vorkommen.

Sei $\pi$ eine Abbildung von den Buchstaben $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ auf die entsprechenden Buchstaben in einer Permutation der $26$ englischen Kleinbuchstaben. Zum Beispiel definiert die Permutation $\texttt{qwertyuiopasdfghjklzxcvbnm}$ die folgende Abbildung:

$$ \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 eine Zeichenkette $u = u_1 u_2 \cdots u_m$ definieren wir

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

Mit der obigen Abbildung gilt beispielsweise $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat möchte, dass das Wörterbuch ein Wort $w$ enthält, sodass nach Anwendung jeder beliebigen solchen Abbildung $\pi$ auf jedes Wort im Wörterbuch $\pi(w)$ im resultierenden Wörterbuch stets das lexikografisch kleinste Wort ist.

Bestimmen Sie für jedes $k = 1, 2, \ldots, n$ die Anzahl der Wörterbücher, die $k$ verschiedene Wörter enthalten und die Bedingung erfüllen, modulo $998\,244\,353$. Zwei Wörterbücher gelten genau dann als verschieden, wenn sie vor Anwendung einer Abbildung unterschiedliche Wortmengen enthalten.

Zur Erinnerung: Eine Zeichenkette $a$ ist lexikografisch kleiner als eine Zeichenkette $b$, wenn $a$ ein Präfix von $b$ ist (und $a \neq b$ gilt) oder wenn ein Index $i$ ($1 \le i \le \min(|a|, |b|)$) existiert, sodass $a_i < b_i$ gilt und für jeden Index $j$ ($1 \le j < i$) $a_j = b_j$ ist.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$ ($1 \le n \le 10^5$).

Die zweite Zeile enthält eine Zeichenkette $S$ der Länge $n$, die ausschließlich aus englischen Kleinbuchstaben besteht.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall $n$ ganze Zahlen in einer Zeile aus. Die $k$-te ganze Zahl gibt die Anzahl der Wörterbücher an, die $k$ verschiedene Wörter enthalten und die Bedingung erfüllen, modulo $998\,244\,353$.

Beispiele

Eingabe 1

3
3
aab
4
ppqq
7
abcaabc

Ausgabe 1

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

Hinweis

Jedes Wörterbuch unten ist als Menge von Wörtern geschrieben.

Für den ersten Testfall $S = \texttt{aab}$ lauten die Wörterbücher, die die Bedingung für $k = 1, 2, 3$ erfüllen: