F. Nun Heh Heh Aaaaaaaaaaa
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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

Example
Input
2
nunhehhehahaahahahahahahaahaahahahahha
nunhehhehhehhahaahahahaahaahahaaaahaa
Output
114514
1919810