Problem H
Hashing Algorithm

You’re researching an equivalence relation on strings. Let $F(A)$ be the multiset of all substrings of $A$, and $G(A)$ be the set of all distinct substrings of $A$. Two strings $A$ and $B$ are isomorphic to each other if there exists a bijective mapping $\phi : G(A) \to G(B)$ such that $\phi (F(A)) = F(B)$.

Unfortunately, there are $O(n^2)$ possible substrings for a string of length $n$, so you decide to use a hashing algorithm to check for isomorphism. The algorithm works as follows:

• Let $F(A)$ be the multiset of all substrings of $A$.

  For example, $F(\texttt{aba}) = \{ \texttt{a}, \texttt{b}, \texttt{a}, \texttt{ab}, \texttt{ba}, \texttt{aba}\} $.

• Let $G(A)$ be the set of all distinct substrings of $A$.

  For example, $G(\texttt{aba}) = \{ \texttt{a}, \texttt{b}, \texttt{ab}, \texttt{ba}, \texttt{aba}\} $.

• Let $C(A, B)$ be the number of substrings of $A$ that is equal to $B$. Equivalently, it is the number of times $B$ occurs in $F(A)$.

  For example, $C(\texttt{aba}, \texttt{a}) = 2$ and $C(\texttt{aba}, \texttt{ab}) = 1$.

• The hash of a string $A$ is defined as $H(A) = \sum _{B \in G(A)} C(A, B)^2 \bmod 998\, 244\, 353$. In other words, it is the sum of the squares of the number of times each distinct substring appears in $A$, modulo $998\, 244\, 353$.

  For example, $H(\texttt{aba}) = 2^2 + 1^2 + 1^2 + 1^2 + 1^2 = 8$.

You have multiple strings $S$, and you want to compute the hash value $H(S)$ for each of them. Find them!

Input

The input starts with a line containing an integer $C$, denoting the number of test cases ($1 \leq C \leq 300\, 000$).

Each test case consists of a single line containing a string $S$, consisting of lowercase English letters ($1 \le |S| \le 300\, 000$). The sum of lengths of all strings over all test cases does not exceed $300\, 000$.

Output

For each test case, output a single line containing an integer $H(S)$, denoting the hash value of $S$.

3
aaa
abc
aba

14
6
8