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$ เป็นอุปสรรค (prefix) ของ $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$ คือ: