codeforces#P1984D. "a" String Problem

    ID: 34738 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>brute forcehashingimplementationmathstring suffix structuresstrings*2000

"a" String Problem

当前没有测试数据。

Description

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.

Input

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$.

Output

For each test case, output a single integer — the number of nonempty strings $t \neq$ "$\texttt{a}$" that satisfy all constraints.

8
aaaaa
baba
cabacb
aaabaaa
bitset
ab
abbaaaabbb
yearnineteeneightyfour
4
4
1
16
1
2
3
1

Note

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.