/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
A, B からなる文字列 S が与えられます．
あなたはこの文字列に対して，次の操作を繰り返し行うことができます：
- S の中の連続する 3 文字であって
AABまたはBAAに等しいものをひとつ選び，その 3 文字を S から削除する（削除した後，残っている文字は連結される）．
操作を行える回数の最大値を求めてください．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\leq T\leq 10^5
- S は
A,Bからなる文字列である． - 1\leq |S|\leq 10^6
- 1 個の入力に含まれるテストケースについて，それらの |S| の総和は 10^6 以下である．
入力
入力は以下の形式で標準入力から与えられます．
T
\text{case}_1
\vdots
\text{case}_T
各テストケースは以下の形式で与えられます．
S
出力
T 行出力してください．i 行目には i 番目のテストケースについて，操作を行える回数の最大値を出力してください．
入力例 1
10 AABAAAB BAAAAABBA A B ABA BAA AAAAAA AAAABB AABABBAABBABAAAABBAA BBAAAAABAAAAABABAABA
出力例 1
2 3 0 0 0 1 0 2 5 6
1 番目，2 番目のテストケースについて，次が操作回数を最大化する方法の一例となります．
AABAAAB→AAAB→ABAAAAABBA→BAAABA→BAA→ （空文字列）
Score: 800 points
Problem Statement
You are given a string S consisting of characters A and B.
On this string, you can repeatedly perform the following operation:
- Choose three consecutive characters in S that are equal to
AABorBAA, and delete those three characters from S (after deletion, the remaining characters are concatenated).
Find the maximum number of times you can perform this operation.
T test cases are given; solve each of them.
Constraints
- 1\leq T\leq 10^5
- S is a string consisting of
AandB. - 1\leq |S|\leq 10^6
- The sum of |S| over all test cases in a single input is at most 10^6.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each test case is given in the following format:
S
Output
Print T lines. The i-th line should contain the maximum number of operations that can be performed for the i-th test case.
Sample Input 1
10 AABAAAB BAAAAABBA A B ABA BAA AAAAAA AAAABB AABABBAABBABAAAABBAA BBAAAAABAAAAABABAABA
Sample Output 1
2 3 0 0 0 1 0 2 5 6
For each of the first and second test cases, here is a possible way to perform the maximum number of operations:
AABAAAB→AAAB→ABAAAAABBA→BAAABA→BAA→ (empty string)