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?


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 20000)$  — the number of test cases. The description of the test cases follows.

Each of the next $t$ lines contains a single test case each, consisting of a non-empty string $s$: the string that Zookeeper needs to bomb. It is guaranteed that all symbols of $s$ are either 'A' or 'B'.

It is guaranteed that the sum of $|s|$ (length of $s$) among all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single integer: the length of the shortest string that Zookeeper can make.


-----Example-----
Input
3
AAA
BABA
AABBBABBBB

Output
3
2
0



-----Note-----

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$.

Difficulty: competition

Starter code:

Solutions:
import sys
readline = sys.stdin.readline

T = int(readline())
Ans = [None]*T
for qu in range(T):
    S = [1 if s == 'A' else 0 for s in readline().strip()]
    stack = []
    for s in S:
        if s:
            stack.append(s)
        else:
            if stack and stack[-1] == 1:
                stack.pop()
            else:
                stack.append(s)
    stack2 = []
    for s in stack:
        if s:
            stack2.append(s)
        else:
            if stack2 and stack2[-1] == 0:
                stack2.pop()
            else:
                stack2.append(s)
    Ans[qu] = len(stack2)

print('\n'.join(map(str, Ans)))


def main():
    # n = int(input())
    # arr = list(map(int, input().split()))
    # x1, y1, x2, y2 = map(int, input().split())
    s = input()
    arr = []
    for i in range(len(s)):
        if len(arr) != 0 and s[i] == 'B':
            arr.pop()
        else:
            arr.append(s[i])
    print(len(arr))


# for _ in range(1):
for _ in range(int(input())):
    main()


gans = []
for _ in range(int(input())):
    s = list(input())
    n = len(s)
    cur = 0
    ans = n
    for i in range(n - 1, -1, -1):
        if s[i] == 'B':
            cur += 1
        else:
            if cur > 0:
                cur -= 1
                ans -= 2
    ans -= cur - cur % 2
    gans.append(ans)
print('\n'.join(map(str, gans)))
        


for t in range(int(input())):
    s=input()
    stack=[]
    for i in s:
        if i=='A':
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                stack.append(i)
    print(len(stack))

import sys
import random
# import numpy as np
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter

# sys.setrecursionlimit(1000000)
# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")

MOD = 10 ** 9 + 7
divide = lambda x: pow(x, MOD - 2, MOD)


def solve():
    S = getS()
    n = len(S)

    ans = 0
    bs = 0
    for c in reversed(S):
        if c == "A":
            if bs:
                ans += 2
                bs -= 1
        else:
            bs += 1

    ans += (bs // 2) * 2

    print(n - ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return


def __starting_point():
    main()
    # solve()

__starting_point()

t=int(input())

for i in range(t):

    s=input()
    stack=[]

    for i in range(len(s)):

        if len(stack)==0:

            stack.append(s[i])

        

        elif s[i]=='B' and (stack[-1]=='A' or stack[-1]=='B'):

                stack.pop()

        else:
            stack.append(s[i])
    print(len(stack))
                


def solve():
    s = input()
    n = len(s)
    acnt = 0
    bcnt = 0
    ans = 0
    for i in s:
        if i == "B":
            if acnt:
                acnt -= 1
            else:
                bcnt += 1
        if i == "A":
            acnt += 1
    print(acnt + bcnt % 2)
for i in range(int(input())):
    solve()

from math import *
from bisect import *
from collections import *
from random import *
from decimal import *
from itertools import *
import sys
input=sys.stdin.readline
def inp():
    return int(input())
def st():
    return input().rstrip('\n')
def lis():
    return list(map(int,input().split()))
def ma():
    return list(map(int,input().split()))
t=inp()
while(t):
    t-=1
    s=st()
    stack=[]
    for i in range(len(s)):
        stack.append(s[i])
        while(len(stack)!=0 and len(stack)-1):
            x=stack[-1]
            y=stack[-2]
            if(x==y=='B' or (x=='B' and y=='A')):
                stack.pop()
                stack.pop()
            else:
                break
    print(len(stack))