{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ consisting of characters `A` and `B`.\nOn this string, you can repeatedly perform the following operation:\n\n*   Choose three consecutive characters in $S$ that are equal to `AAB` or `BAA`, and delete those three characters from $S$ (after deletion, the remaining characters are concatenated).\n\nFind the maximum number of times you can perform this operation.\n$T$ test cases are given; solve each of them."},{"iden":"constraints","content":"*   $1\\leq T\\leq 10^5$\n*   $S$ is a string consisting of `A` and `B`.\n*   $1\\leq |S|\\leq 10^6$\n*   The sum of $|S|$ over all test cases in a single input is at most $10^6$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$S$"},{"iden":"sample input 1","content":"10\nAABAAAB\nBAAAAABBA\nA\nB\nABA\nBAA\nAAAAAA\nAAAABB\nAABABBAABBABAAAABBAA\nBBAAAAABAAAAABABAABA"},{"iden":"sample output 1","content":"2\n3\n0\n0\n0\n1\n0\n2\n5\n6\n\nFor each of the first and second test cases, here is a possible way to perform the maximum number of operations:\n\n*   `AABAAAB` → `AAAB` → `A`\n*   `BAAAAABBA` → `BAAABA` → `BAA` → (empty string)"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}