AT_arc224_e [ARC224E] ABC|AB|A

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.

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 $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 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. ### 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 $ .