VegiCat-та $n$ кіші ағылшын әріптерінен тұратын $S$ жолы бар. Ол сөздері ретінде $S$ жолының өзара әртүрлі $k$ бос емес ішкі жолын қамтитын сөздік құрастырғысы келеді. Ішкі жол дегеніміз — жолдың біртұтас бөлігі. Мазмұны бірдей ішкі жолдар $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 сөздіктегі әрбір сөзге осындай кез келген $\pi$ бейнелеуін қолданғаннан кейін, нәтижесінде алынған сөздікте $\pi(w)$ әрқашан лексикографиялық тұрғыдан ең кіші сөз болатындай $w$ сөзінің сөздікте болғанын қалайды.

Әрбір $k = 1, 2, \ldots, n$ үшін $k$ әртүрлі сөзден тұратын және талапты қанағаттандыратын сөздіктер санын $998\,244\,353$ модулі бойынша табыңыз. Екі сөздік кез келген бейнелеу қолданылғанға дейін әртүрлі сөздер жиынын қамтыса және тек сонда ғана әртүрлі болып есептеледі.

Еске сала кетейік, егер $a$ жолы $b$ жолының префиксі болса (және $a \neq b$), немесе $a_i < b_i$ болатындай және кез келген $j$ ($1 \le j < i$) индексі үшін $a_j = b_j$ орындалатындай $i$ ($1 \le i \le \min(|a|, |b|)$) индексі табылса, онда $a$ жолы лексикографиялық тұрғыдан $b$ жолынан кіші болады.

Енгізу деректері

Бірінші жолда тест жағдайларының санын білдіретін бүтін сан $T$ ($1 \le T \le 10^4$) берілген. Одан кейін тест жағдайларының сипаттамасы беріледі.

Әрбір тест жағдайының бірінші жолында бүтін сан $n$ ($1 \le n \le 10^5$) берілген.

Екінші жолда тек кіші ағылшын әріптерінен тұратын ұзындығы $n$ болатын $S$ жолы берілген.

Барлық тест жағдайлары бойынша $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$ болғанда талапты қанағаттандыратын сөздіктер: