409369: GYM103492 F Nun Heh Heh Aaaaaaaaaaa

Vasily Tadokorov is a stringologist. He thinks a string is fragrant if it can be divided into two parts — nunhehheh as the prefix and a number of (excluding $$$0$$$) a as the suffix. For example, nunhehhehaaaaaa is fragrant, but nunhehheh and 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.

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

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

2
nunhehhehahaahahahahahahaahaahahahahha
nunhehhehhehhahaahahahaahaahahaaaahaa

114514
1919810