← 返回题目列表

Codeforces · 1984/D

D. ''a'' 字符串问题

中文机器翻译题面 查看原题

给您一个由小写拉丁字符组成的字符串 $$$s$$$。计算非空字符串 $$$t \neq$$$ "$$$\texttt{a}$$$" 的数量,以便可以将 $$$^{\dagger}$$$ $$$s$$$ 划分为满足以下条件的一些子字符串:

- 每个子字符串等于 $$$t$$$ 或 "$$$\texttt{a}$$$",并且
- 至少一个子字符串等于 $$$t$$$。

$$$^{\dagger}$$$ 字符串 $$$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 \cdot 10^5$$$)。

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

输出

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

示例

输入 #1

8
aaaaa
baba
cabacb
aaabaaa
bitset
ab
abbaaaabbb
yearnineteeneightyfour

输出 #1

4
4
1
16
1
2
3
1

注意

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

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

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