AT_arc224_e [ARC224E] ABC|AB|A

`A`, `B`, `C` からなる文字列 $ S $ が与えられます。 以下の操作を $ 0 $ 回以上何回でも行えます。 - $ S $ から `A` または `AB` または `ABC` である部分文字列 (連続部分列) を $ 1 $ つ選択して削除する。残った文字は順序を保って連結される。 最終的な $ S $ の長さとして達成可能な最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

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

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

### Sample Explanation 1 この入力には $ 5 $ 個のテストケースが含まれています。 $ 1 $ 個目のテストケースについて、例えば以下のように操作を行うことができます。 - $ S= $ `CAABCB` の $ 3 $ 文字目から $ 5 $ 文字目を選択して削除する。操作後に $ S $ は `CAB` となる。 - $ S= $ `CAB` の $ 2 $ 文字目から $ 3 $ 文字目を選択して削除する。操作後に $ S $ は `C` となる。 - これ以上操作を行うことはできない。 $ S= $ `C` の長さは $ 1 $ であり、これが達成可能な最小です。 ### Constraints - $ T $ は $ 1 $ 以上 $ 10^5 $ 以下の整数 - $ S $ は `A`, `B`, `C` からなる長さ $ 1 $ 以上 $ 10^6 $ 以下の文字列 - ひとつの入力における $ |S| $ の総和は $ 10^6 $ 以下