VegiCat memiliki sebuah string $S$ yang terdiri dari $n$ huruf kecil bahasa Inggris. Ia ingin membangun sebuah kamus yang berisi $k$ substring tak kosong yang berbeda dari $S$ sebagai kata-katanya. Substring adalah bagian berurutan yang kontigu dari sebuah string. Substring dengan isi yang sama dianggap sebagai kata yang sama, meskipun muncul pada posisi yang berbeda di dalam $S$.

Misalkan $\pi$ adalah pemetaan dari huruf-huruf $\texttt{a}, \texttt{b}, \ldots, \texttt{z}$ ke huruf-huruf yang bersesuaian dalam suatu permutasi dari $26$ huruf kecil bahasa Inggris. Sebagai contoh, permutasi $\texttt{qwertyuiopasdfghjklzxcvbnm}$ mendefinisikan pemetaan berikut:

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

Untuk sebuah string $u = u_1 u_2 \cdots u_m$, definisikan

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

Sebagai contoh, dengan pemetaan di atas, $\pi(\texttt{apple}) = \texttt{qhhst}$.

VegiCat menginginkan kamus tersebut memuat sebuah kata $w$ sedemikian sehingga setelah menerapkan pemetaan $\pi$ apa pun seperti itu pada setiap kata di dalam kamus, $\pi(w)$ selalu menjadi kata terkecil secara leksikografis dalam kamus yang dihasilkan.

Untuk setiap $k = 1, 2, \ldots, n$, carilah banyaknya kamus yang memuat $k$ kata berbeda dan memenuhi syarat tersebut, modulo $998\,244\,353$. Dua kamus dianggap berbeda jika dan hanya jika keduanya memuat himpunan kata yang berbeda sebelum pemetaan apa pun diterapkan.

Ingat kembali bahwa string $a$ lebih kecil secara leksikografis daripada string $b$ jika $a$ adalah prefiks dari $b$ (dan $a \neq b$), atau terdapat suatu indeks $i$ ($1 \le i \le \min(|a|, |b|)$) sehingga $a_i < b_i$, dan untuk setiap indeks $j$ ($1 \le j < i$) berlaku $a_j = b_j$.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$).

Baris kedua berisi sebuah string $S$ dengan panjang $n$, yang hanya terdiri dari huruf kecil bahasa Inggris.

Dijamin bahwa jumlah $n$ di semua kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan $n$ bilangan bulat dalam satu baris. Bilangan bulat ke-$k$ menyatakan banyaknya kamus yang memuat $k$ kata berbeda dan memenuhi syarat, 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

Catatan

Setiap kamus di bawah ini ditulis sebagai himpunan kata.

Untuk kasus uji pertama, $S = \texttt{aab}$, kamus-kamus yang memenuhi syarat untuk $k = 1, 2, 3$ adalah: