ל-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$.

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

הערה

כל מילון להלן נכתב כקבוצת מילים.

עבור מקרה הבדיקה הראשון, $S = \texttt{aab}$, המילונים המקיימים את הדרישה עבור $k = 1, 2, 3$ הם: