CF1428C ABBB

Zookeeper is playing a game. In this game, Zookeeper must use bombs to bomb a string that consists of letters 'A' and 'B'. He can use bombs to bomb a substring which is either "AB" or "BB". When he bombs such a substring, the substring gets deleted from the string and the remaining parts of the string get concatenated. For example, Zookeeper can use two such operations: AABABBA $ \to $ AABBA $ \to $ AAA. Zookeeper wonders what the shortest string he can make is. Can you help him find the length of the shortest string?

N/A

N/A

For the first test case, you can't make any moves, so the answer is $ 3 $ . For the second test case, one optimal sequence of moves is BABA $ \to $ BA. So, the answer is $ 2 $ . For the third test case, one optimal sequence of moves is AABBBABBBB $ \to $ AABBBABB $ \to $ AABBBB $ \to $ ABBB $ \to $ AB $ \to $ (empty string). So, the answer is $ 0 $ .