CF1984D."a" String Problem

给定一个由小写拉丁字母组成的字符串 $s$。请计算有多少个非空字符串 $t \neq \texttt{"a"}$，使得可以将 $s$ 分割成若干子串，满足以下条件：

• 每个子串要么等于 $t$，要么等于 $\texttt{"a"}$；
• 至少有一个子串等于 $t$。

一个字符串 $s$ 的分割是一个有序的 $k$ 个字符串 $t_1, t_2, \ldots, t_k$（称为子串）的序列，满足 $t_1 + t_2 + \ldots + t_k = s$，其中 $+$ 表示连接操作。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例仅一行，包含一个由小写拉丁字母组成的字符串 $s$（$2 \leq |s| \leq 2 \times 10^5$）。

所有测试用例中 $|s|$ 的总和不超过 $3 \times 10^5$。

对于每个测试用例，输出一个整数，表示满足所有约束条件的非空字符串 $t \neq \texttt{"a"}$ 的数量。

在第一个测试用例中，$t$ 可以是 $\texttt{aa}$、$\texttt{aaa}$、$\texttt{aaaa}$ 或整个字符串。

在第二个测试用例中，$t$ 可以是 $\texttt{b}$、$\texttt{bab}$、$\texttt{ba}$ 或整个字符串。

在第三个测试用例中，唯一满足条件的 $t$ 是整个字符串。

由 ChatGPT 4.1 翻译