У ВегіКета є рядок $S$ із $n$ малих літер англійського алфавіту. Він хоче скласти словник, що містить як слова $k$ різних непорожніх підрядків рядка $S$. Підрядком називається неперервний фрагмент рядка. Підрядки з однаковим вмістом вважаються одним і тим самим словом, навіть якщо вони зустрічаються на різних позиціях у $S$.

Нехай $\pi$ — відображення з літер $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ у відповідні літери деякої перестановки $26$ малих літер англійського алфавіту. Наприклад, перестановка $\texttt{qwertyuiopasdfghjklzxcvbnm}$ задає таке відображення:

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

Для рядка $u = u_1 u_2 \cdots u_m$ визначимо

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

Наприклад, для наведеного вище відображення $\pi(\texttt{apple}) = \texttt{qhhst}$.

ВегіКет хоче, щоб словник містив таке слово $w$, що після застосування будь-якого такого відображення $\pi$ до кожного слова у словнику рядок $\pi(w)$ завжди був лексикографічно найменшим словом в отриманому словнику.

Для кожного $k = 1, 2, \ldots, n$ знайдіть кількість словників, які містять $k$ різних слів і задовольняють вимогу, за модулем $998\,244\,353$. Два словники вважаються різними тоді й лише тоді, коли до застосування будь-якого відображення вони містять різні множини слів.

Нагадаємо, що рядок $a$ лексикографічно менший за рядок $b$, якщо $a$ є префіксом $b$ (і $a \neq b$), або існує такий індекс $i$ ($1 \le i \le \min(|a|, |b|)$), що $a_i < b_i$, а для будь-якого індексу $j$ ($1 \le j < i$) виконується $a_j = b_j$.

Вхідні дані

Перший рядок містить ціле число $T$ ($1 \le T \le 10^4$) — кількість наборів вхідних даних. Далі йдуть описи наборів вхідних даних.

Перший рядок кожного набору вхідних даних містить ціле число $n$ ($1 \le n \le 10^5$).

Другий рядок містить рядок $S$ довжини $n$, що складається лише з малих літер англійського алфавіту.

Гарантується, що сума $n$ за всіма наборами вхідних даних не перевищує $10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть в одному рядку $n$ цілих чисел. $k$-те ціле число позначає кількість словників, що містять $k$ різних слів і задовольняють вимогу, за модулем $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

Примітка

Кожен словник нижче записано як множину слів.

Для першого набору вхідних даних, $S = \texttt{aab}$, словники, що задовольняють вимогу для $k = 1, 2, 3$, є такими: