Problem Description

Recently, Yiwen is learning Assembly Language.

Since Yiwen is a genius in computer science, he proposed an extremely valuable technique called Basic Instruction Technology. Using this kind of technique, Yiwen can create numerous different instruction. Some of these instruction can be used to calculate some special eigenvalue of a string, such as $sqc$.

For a string $s$, let $s_i$ be the $i^{th}$ character of it.

Instruction sqc has 4 operands $s$, $l$, $r$ and $c$, where $s$ is a string, $1 \leq l \leq r \leq n$, $c$ is a character represented by ASCII value. $sqc(s,l,r,c)$ returns the number of character $c$ in substring $s_l \cdots s_r$.

Yiwen wants you to calculate following expression for the given string $s$: $$\sum_{c=97}^{122}\sum_{i=1}^{n}\sum_{j=i}^{n} sqc(s,i,j,c)^2$$

Note that the ASCII value of 'a' is $97$ and the ASCII value of 'z' is $122$.

The answer will probably be very huge, so just calculate the answer modulo $998244353$.

Input

The input consists of multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 100$) -- the number of test cases.

For each test case, the only line contains a string $s$ ($|s| \leq 10^5$) consists of lowercase English letters.

It is guaranteed that the sum of $|s|$ over all test cases does not excceed $5 \times 10^6$.

Output

For each test case, output your answer modulo $998244353$ in a single line.

5
ababa
a
abcdefga
afidhehfhd
ggggggggggg

57
1
122
328
1716