У ВегиКэта есть строка $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$.

Примеры

Входные данные 1

3
3
aab
4
ppqq
7
abcaabc

Выходные данные 1

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

Примечание

Каждый словарь ниже записан как множество слов.

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