D. “a” 字符串问题

时间限制：2 秒
内存限制：256 兆字节

给定一个由小写拉丁字母组成的字符串 $s$。统计满足以下条件的非空字符串 $t \neq \text{"a"}$ 的个数：

• 可以将 $s$ 划分为若干子串，使得每个子串要么等于 $t$，要么等于 $\text{"a"}$，并且
• 至少有一个子串等于 $t$。

这里，划分是指将 $s$ 表示为子串的拼接 $t_1 + t_2 + \dots + t_k = s$，其中 $+$ 表示拼接运算。

输入

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

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

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

输出

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

示例

输入

8
aaaaa
baba
cabacb
aaabaaa
bitset
ab
abbaaaabbb
yearnineteeneightyfour

输出

4
4
1
16
1
2
3
1

注释

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

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

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