{"problem":{"name":"Delete AAB or BAA","description":{"content":"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 `","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc066_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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$.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc066_c","tags":[],"sample_group":[["10\nAABAAAB\nBAAAAABBA\nA\nB\nABA\nBAA\nAAAAAA\nAAAABB\nAABABBAABBABAAAABBAA\nBBAAAAABAAAAABABAABA","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)"]],"created_at":"2026-03-03 11:01:14"}}