Problem D
Decision Making

After getting introduced to gambling by your friends, you decided to try your luck at the casino. There, you encountered a very interesting game!

The game is played with a single coin and a set of $n$ strings $s_1, s_2, \ldots , s_ n$ consisting of the characters H and T. The coin will be flipped multiple times until a winner among the $n$ strings is determined.

Suppose the sequence of coin flips results in the string $v$, where $v_ i = \texttt{H}$ if the $i$-th coin flip results in heads and $v_ i = \texttt{T}$ if the $i$-th coin flip results in tails.

Then, a winner is determined if there exists a string $s_ i$ which occurs as a substring of $v$. If no such string exists, the game continues. If there are multiple such strings, then the winner is the string with the smallest index.

For example, suppose $s_1 = \texttt{HTT}$, $s_2 = \texttt{TTT}$, $s_3 = \texttt{HT}$, and $s_4 = \texttt{TTT}$.

• If $v = \texttt{TT}$, then no winner has been determined and the game continues.

• If $v = \texttt{TTHT}$, then the winner is $s_3$.

• If $v = \texttt{TTT}$, then the winner is $s_2$, since it has a smaller index than $s_4$.

Note that $s_1$ can never be a winner, since if $s_1$ occurs as a substring of $v$, then $s_3$ will have occurred earlier as a substring of $v$. In this example, the probability of $s_2$ winning is $\frac{1}{8}$ and the probability of $s_3$ winning is $\frac{7}{8}$.

You don’t believe in the concept of luck, so you decide to compute the exact probability of winning for every string $s_ i$. Fortunately, you know that the coin is fair, so the probability of getting heads or tails is $\frac{1}{2}$ each.

It is guaranteed that the probability of winning for each string $s_ i$ can be represented as a rational number $\frac{P_ i}{Q_ i}$, where $Q_ i$ is coprime to $998\, 244\, 353$. You should output the value of $P_ i \cdot Q_ i^{-1} \bmod 998\, 244\, 353$ for each string.

Input

The first line of input contains one integer $n$, the number of strings ($1 \leq n \leq 100$).

The next $n$ lines of input contains the string $s_ i$ consisting of the characters H and T ($1 \leq |s_ i| \leq 100\, 000$). The sum of the lengths of all strings does not exceed $100\, 000$.

It is guaranteed that the probability of winning for each string $s_ i$ can be represented as a rational number $\frac{P_ i}{Q_ i}$, where $Q_ i$ is coprime to $998\, 244\, 353$.

Output

Output $n$ lines, where the $i$-th line contains the value of $P_ i \cdot Q_ i^{-1} \bmod 998\, 244\, 353$ — the probability of winning for the string $s_ i$.

Explanation of Sample

For the first sample, the probability of winning for each string is as follows:

• $s_1$ wins with probability $0$.

• $s_2$ wins with probability $\frac{1}{8}$.

• $s_3$ wins with probability $\frac{7}{8}$.

• $s_4$ wins with probability $0$.

For the second sample, the probability of winning for each string is as follows:

• $s_1$ wins with probability $\frac{7}{302} \approx 0.023179$.

• $s_2$ wins with probability $\frac{148}{302} \approx 0.490066$.

• $s_3$ wins with probability $\frac{147}{302} \approx 0.486755$.

4
HTT
TTT
HT
TTT

0 873463809 124780545 0

3
HTHTHTHT
THHT
HTTH

135523240 13221780 849499334