لدى VegiCat سلسلة نصية $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}$.

يريد VegiCat أن يحتوي القاموس على كلمة $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$ هي: