D. ""a"" String Problem
brute force; hashing; implementation; math; string suffix structures; strings
You are given a string \(s\) consisting of lowercase Latin characters. Count the number of nonempty strings \(t \neq\) ""\(\texttt{a}\)"" such that it is possible to partition\(^{\dagger}\) \(s\) into some substrings satisfying the following conditions: each substring either equals \(t\) or ""\(\texttt{a}\)"", and at least one substring equals \(t\). \(^{\dagger}\) A partition of a string \(s\) is an ordered sequence of some \(k\) strings \(t_1, t_2, \ldots, t_k\) (called substrings) such that \(t_1 + t_2 + \ldots + t_k = s\), where \(+\) represents the concatenation operation.
The first line contains a single integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases.The only line of each test case contains a string \(s\) consisting of lowercase Latin characters (\(2 \leq |s| \leq 2 \cdot 10^5\)).The sum of \(|s|\) over all test cases does not exceed \(3 \cdot 10^5\).
For each test case, output a single integer — the number of nonempty strings \(t \neq\) ""\(\texttt{a}\)"" that satisfy all constraints.
In the first test case, \(t\) can be ""\(\texttt{aa}\)"", ""\(\texttt{aaa}\)"", ""\(\texttt{aaaa}\)"", or the full string.In the second test case, \(t\) can be ""\(\texttt{b}\)"", ""\(\texttt{bab}\)"", ""\(\texttt{ba}\)"", or the full string.In the third test case, the only such \(t\) is the full string.