Description

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.