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.

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.

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.

''a'' String Problem

Examples