Problem Description

Vasily Tadokorov is a stringologist. He thinks a string is fragrant if it can be divided into two parts — $\texttt{nunhehheh}$ as the prefix and a number of (excluding $0$) $\texttt{a}$ as the suffix. For example, $\texttt{nunhehhehaaaaaa}$ is fragrant, but $\texttt{nunhehheh}$ and $\texttt{nunhehhehoooaaa}$ are not fragrant.

Today Vasily Tadokorov has some strings consisting of lowercase English letters. For each string, he wants to know how many subsequences of this string are fragrant. A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (including $0$) characters.

Input

The first line contains an integer $T\ (1 \leq T \leq 1000)$, denoting the number of strings.

Each of the next $T$ lines contains a string $S\ (1 \leq |S| \leq 10^5)$ consisting of lowercase English letters.

The total length of the strings in the input will not exceed $10^6$.

Output

For each of the given $T$ strings, output the answer modulo $998244353$.

2
nunhehhehahaahahahahahahaahaahahahahha
nunhehhehhehhahaahahahaahaahahaaaahaa

114514
1919810