E - ABC|AB|A 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

A, B, C からなる文字列 S が与えられます。

以下の操作を 0 回以上何回でも行えます。

  • S から A または AB または ABC である部分文字列 (連続部分列) を 1 つ選択して削除する。残った文字は順序を保って連結される。

最終的な S の長さとして達成可能な最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • T は 1 以上 10^5 以下の整数
  • S は A, B, C からなる長さ 1 以上 10^6 以下の文字列
  • ひとつの入力における |S| の総和は 10^6 以下

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 個目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

S

出力

T 行出力せよ。i 行目には i 個目のテストケースの答えを出力せよ。

入力例 1

5
CAABCB
B
AAABBC
AABBCC
CABCCBCBAABCBBBAABAABACABBC

出力例 1

1
1
0
1
7

この入力には 5 個のテストケースが含まれています。

1 個目のテストケースについて、例えば以下のように操作を行うことができます。

  • S= CAABCB の 3 文字目から 5 文字目を選択して削除する。操作後に S は CAB となる。
  • S= CAB の 2 文字目から 3 文字目を選択して削除する。操作後に S は C となる。
  • これ以上操作を行うことはできない。 S= C の長さは 1 であり、これが達成可能な最小です。

Score : 500 points

Problem Statement

You are given a string S consisting of A, B, and C.

You can perform the following operation zero or more times.

  • Choose a substring (contiguous subsequence) of S that is A, AB, or ABC, and delete it. The remaining characters are concatenated, preserving their order.

Find the minimum possible length of S in the end.

T test cases are given; solve each of them.

Constraints

  • T is an integer between 1 and 10^5, inclusive.
  • S is a string consisting of A, B, and C with length between 1 and 10^6, inclusive.
  • The sum of |S| in each input is at most 10^6.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

S

Output

Output T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 1

5
CAABCB
B
AAABBC
AABBCC
CABCCBCBAABCBBBAABAABACABBC

Sample Output 1

1
1
0
1
7

This input contains five test cases.

For the first test case, we can perform the operations as follows, for example.

  • Choose and delete the third through fifth characters of S= CAABCB. After the operation, S becomes CAB.
  • Choose and delete the second through third characters of S= CAB. After the operation, S becomes C.
  • No further operations can be performed. S= C has length 1, which is the minimum achievable.