Alex is a private jewel collector.
Recently, he purchased a piece of jewelry, a bunch of $$$n$$$ gemstones. The gemstones have $$$26$$$ different types, labeled from a to z. He wants to split the jewelry and combine them into a jewel matrix.
Alex will choose $$$d \in \{1,2,\cdots, n\}$$$, the width of the jewel matrix. Then, he will split the jewelry and get $$$\left\lfloor \frac{n}{d} \right\rfloor$$$ bunches of gemstones with length $$$d$$$ and a bunch of length $$$n \bmod d$$$ if $$$d$$$ doesn't divide $$$n$$$. All $$$\left\lfloor \frac{n}{d} \right\rfloor$$$ bunches with length $$$d$$$ will be permuted as rows of the jewel matrix.
Alex wonders how many different jewel matrix he can get. Two jewel matrix are considered different if and only if they have different width, or it is at least one row different.
As the results can be very large, output it modulo $$$998244353$$$.
The first line of the input gives the number of test cases, $$$T\ (1\le T \le 1000)$$$. $$$T$$$ test cases follow.
For each test case, the only line contains a string $$$s_1s_2\cdots s_n\ (1\le n \le 3 \times 10^5, s_i \in \{\texttt{a,b,c},\cdots,\texttt{z}\})$$$, representing the jewelry.
The sum of $$$n$$$ in all test cases doesn't exceed $$$10^6$$$.
For each test case, output one line containing "Case #x: y", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\texttt{y}$$$ is the answer modulo $$$998244353$$$.
2 ababccd aab
Case #1: 661 Case #2: 6
