Yiwen with Sqc

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.

Sample Input

5

ababa

a

abcdefga

afidhehfhd

ggggggggggg

Sample Output

57

1

122

328

1716

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（7）