VegiCat은 $n$개의 영어 소문자로 이루어진 문자열 $S$를 가지고 있다. 그는 $S$의 서로 다른 $k$개의 비어 있지 않은 부분 문자열을 단어로 포함하는 사전을 만들고 싶어 한다. 부분 문자열이란 문자열의 연속된 일부분을 뜻한다. 내용이 같은 부분 문자열은 $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}$이다.

VegiCat은 사전의 모든 단어에 이러한 임의의 매핑 $\pi$를 적용한 후에도, 결과 사전에서 $\pi(w)$가 항상 사전순으로 가장 작은 단어가 되도록 하는 단어 $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$)이 주어진다.

두 번째 줄에는 영어 소문자로만 이루어진 길이 $n$인 문자열 $S$가 주어진다.

모든 테스트 케이스에서 $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$에 대해 조건을 만족하는 사전들은 다음과 같다: