VegiCat có một xâu $S$ gồm $n$ chữ cái tiếng Anh viết thường. Cậu muốn xây dựng một từ điển chứa $k$ xâu con khác rỗng phân biệt của $S$ làm các từ của nó. Một xâu con là một đoạn liên tiếp của xâu. Các xâu con có cùng nội dung được coi là cùng một từ, ngay cả khi chúng xuất hiện ở các vị trí khác nhau trong $S$.

Gọi $\pi$ là một ánh xạ từ các chữ cái $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ tới các chữ cái tương ứng trong một hoán vị của $26$ chữ cái tiếng Anh viết thường. Ví dụ, hoán vị $\texttt{qwertyuiopasdfghjklzxcvbnm}$ xác định ánh xạ sau:

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

Đối với một xâu $u = u_1 u_2 \cdots u_m$, định nghĩa

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

Ví dụ, với ánh xạ ở trên, $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat muốn từ điển chứa một từ $w$ sao cho sau khi áp dụng bất kỳ ánh xạ $\pi$ nào như vậy lên mọi từ trong từ điển, $\pi(w)$ luôn là từ có thứ tự từ điển nhỏ nhất trong từ điển thu được.

Với mỗi $k = 1, 2, \ldots, n$, hãy tìm số lượng từ điển chứa $k$ từ phân biệt và thỏa mãn yêu cầu, lấy phần dư cho $998\,244\,353$. Hai từ điển được coi là khác nhau khi và chỉ khi chúng chứa hai tập hợp từ khác nhau trước khi áp dụng bất kỳ ánh xạ nào.

Nhắc lại rằng xâu $a$ có thứ tự từ điển nhỏ hơn xâu $b$ nếu $a$ là một tiền tố của $b$ (và $a \neq b$), hoặc tồn tại một chỉ số $i$ ($1 \le i \le \min(|a|, |b|)$) sao cho $a_i < b_i$, và với mọi chỉ số $j$ ($1 \le j < i$) thì $a_j = b_j$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$), là số lượng bộ dữ liệu. Tiếp theo là mô tả của các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($1 \le n \le 10^5$).

Dòng thứ hai chứa một xâu $S$ có độ dài $n$, chỉ gồm các chữ cái tiếng Anh viết thường.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra $n$ số nguyên trên một dòng. Số nguyên thứ $k$ biểu thị số lượng từ điển chứa $k$ từ phân biệt và thỏa mãn yêu cầu, lấy phần dư cho $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

3
3
aab
4
ppqq
7
abcaabc

Dữ liệu ra 1

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

Ghi chú

Mỗi từ điển dưới đây được viết dưới dạng một tập hợp các từ.

Đối với bộ dữ liệu đầu tiên, $S = \texttt{aab}$, các từ điển thỏa mãn yêu cầu với $k = 1, 2, 3$ là: