409369: GYM103492 F Nun Heh Heh Aaaaaaaaaaa

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Nun Heh Heh Aaaaaaaaaaatime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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$$$.

ExampleInput
2
nunhehhehahaahahahahahahaahaahahahahha
nunhehhehhehhahaahahahaahaahahaaaahaa
Output
114514
1919810

加入题单

上一题 下一题 算法标签: