CF1984D "a" String Problem

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.