该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

The tengu races across Gensokyo at the highest speed together with the crows.

As the newspaper extras fly about, Gensokyo's newspaper girl Aya Shameimaru looked for youkai to serve as story material.

Erahc feels Syameimaru Aya is very cute. What concerns Erahc even more is that, Aya has a habit of frequently adding ayayaya or similar sounds when she speaks. Erahc wants to find out the upper limit of how many times she uses such a pet phrase.

Since Erahc knows little about algorithms, so he leaves the problem to you.

Formally, you are given $T$ strings, each representing something Aya has said. For each string, count how many substrings match the regex pattern a(ya)+ — that is, substrings like aya, ayaya, ayayaya and so on.

Note that overlapping occurrences are allowed and should be counted. For example, in ayaya, the substrings aya (starting at position 1) and aya (starting at position 3) both count.

Format

Input

The first line contains a single integer $T\,(1\leq T\leq 10^3)$, the number of test cases.

The next $T$ lines, each contains a non-empty string $s$ ($1 \leq |s| \leq 10^7$), consisting of visible ASCII characters (including spaces).

The total length across all strings $s$ does not exceed $2\times 10^7$.

Output

For each test case, output a single integer, representing the number of substrings.

Samples

5
a
ya
Syameimaru aya!
ayayayaya
oayaoayayaoyaay.

0
0
1
10
4