VegiCat has a string $S$ of $n$ lowercase English letters. He wants to build a dictionary that contains $k$ distinct nonempty substrings of $S$ as its words. A substring is a contiguous part of a string. Substrings with the same content are treated as the same word, even if they occur at different positions in $S$.

Let $\pi$ be a mapping from the letters $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ to the corresponding letters in a permutation of the $26$ lowercase English letters. For example, the permutation $\texttt{qwertyuiopasdfghjklzxcvbnm}$ defines the following mapping:

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

For a string $u = u_1 u_2 \cdots u_m$, define

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

For example, with the mapping above, $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat wants the dictionary to contain a word $w$ such that, after applying any such mapping $\pi$ to every word in the dictionary, $\pi(w)$ is always the lexicographically smallest word in the resulting dictionary.

For each $k = 1, 2, \ldots, n$, find the number of dictionaries that contain $k$ distinct words and satisfy the requirement, modulo $998\,244\,353$. Two dictionaries are considered different if and only if they contain different sets of words before any mapping is applied.

Recall that string $a$ is lexicographically smaller than string $b$ if $a$ is a prefix of $b$ (and $a \neq b$), or there exists an index $i$ ($1 \le i \le \min(|a|, |b|)$) such that $a_i < b_i$, and for any index $j$ ($1 \le j < i$) $a_j = b_j$.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$).

The second line contains a string $S$ of length $n$, consisting only of lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output $n$ integers on one line. The $k$-th integer represents the number of dictionaries that contain $k$ distinct words and satisfy the requirement, 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

Note

Each dictionary below is written as a set of words.

For the first test case, $S = \texttt{aab}$, the dictionaries that satisfy the requirement for $k = 1, 2, 3$ are: