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 → AABBA → 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 ≤ t ≤ 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 ⋅ 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 → BA. So, the answer is 2.

For the third test case, one optimal sequence of moves is AABBBABBBB → AABBBABB → AABBBB → ABBB → AB → (empty string). So, the answer is 0.
/*
 
    /$$$$$  /$$$$$$  /$$    /$$  /$$$$$$                                                                  
   |__  $$ /$$__  $$ |$$    |$$ /$$__  $$                                                                 
          | $$| $$  \ $$|    $$|$$| $$  \ $$                                                                 
          | $$| $$$$$$$$|  $$ / $$/| $$$$$$$$                                                                 
/ $$  | $$| $$__  $$ \  $$ $$/ | $$__  $$                                                                 
| $$  | $$| $$  | $$  \  $$$/  | $$  | $$                                                                 
|  $$$$$$/| $$  | $$   \  $/   | $$  | $$                                                                 
 \______/ |__/  |__/    \_/    |__/  |__/    
 
/$$$$$$$  /$$$$$$$   /$$$$$$   /$$$$$$  /$$$$$$$   /$$$$$$  /$$      /$$ /$$      /$$ /$$$$$$$$ /$$$$$$$ 
| $$__  $$| $$__  $$ /$$__  $$ /$$__  $$| $$__  $$ /$$__  $$| $$$    /$$$| $$$    /$$$| $$_____/| $$__  $$
| $$  \ $$| $$  \ $$| $$  \ $$| $$  \__/| $$  \ $$| $$  \ $$| $$$$  /$$$$| $$$$  /$$$$| $$      | $$  \ $$
| $$$$$$$/| $$$$$$$/| $$  | $$| $$ /$$$$| $$$$$$$/| $$$$$$$$| $$ $$/$$ $$| $$ $$/$$ $$| $$$$$   | $$$$$$$/
| $$____/ | $$__  $$| $$  | $$| $$|_  $$| $$__  $$| $$__  $$| $$  $$$| $$| $$  $$$| $$| $$__/   | $$__  $$
| $$      | $$  \ $$| $$  | $$| $$  \ $$| $$  \ $$| $$  | $$| $$\  $ | $$| $$\  $ | $$| $$      | $$  \ $$
| $$      | $$  | $$|  $$$$$$/|  $$$$$$/| $$  | $$| $$  | $$| $$ \/  | $$| $$ \/  | $$| $$$$$$$$| $$  | $$
|__/      |__/  |__/ \______/  \______/ |__/  |__/|__/  |__/|__/     |__/|__/     |__/|________/|__/  |__/
                                                                                                                                                                                                                
                                                                                                                                                                                                                
 
*/
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
 public class codeforces
{
    static void shuffle( int arr[])
    {
        int n = arr.length;
        Random r = new Random();
         
       for (int i = n-1; i > 0; i--) {
           int j = r.nextInt(i+1);
             
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    static void shuffle( int arr[][])
    {
        int n = arr.length;
        Random r = new Random();
         
       for (int i = n-1; i > 0; i--) {
           int j = r.nextInt(i+1);
             
            int[] temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        }
        int[][] tdiarr(int m , int n){
            int[][] a = new int[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    a[i][j]=Integer.parseInt(next());
                }
            }
            return a;
        } 
        int[] niarr(int n)
        {
            int[] a = new int[n];
            for(int i=0;i<n;i++)a[i]=Integer.parseInt(next());
            return a;
        }
        long[] nlarr(int n)
        {
            long[] a = new long[n];
            for(int i=0;i<n;i++)a[i]=Long.parseLong(next());
            return a;
        }
        char[] ncarr(){
            return next().trim().toCharArray();
            
            
        }
        
  
        int ni() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nl() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nd() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nstr() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
    
    static void SegmentTree(int arr[], int n)
    {
        // Allocate memory for segment tree
        //Height of segment tree
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
 
        //Maximum size of segment tree
        int max_size = 2 * (int) Math.pow(2, x) - 1;
 
         int[] st = new int[max_size]; // Memory allocation
 
        constructSTUtil(arr, 0, n - 1, 0);
    }
    static int constructSTUtil(int arr[], int ss, int se, int si)
    {
        // If there is one element in array, store it in current node of
        // segment tree and return
        if (ss == se) {
            st[si] = arr[ss];
            return arr[ss];
        }
 
        // If there are more than one elements, then recur for left and
        // right subtrees and store the sum of values in this node
        int mid = getMid(ss, se);
        st[si] = Math.min(constructSTUtil(arr, ss, mid, si * 2 + 1) ,
                 constructSTUtil(arr, mid + 1, se, si * 2 + 2));
        return st[si];
    }
    static int getMid(int s, int e) {
        return s + (e - s) / 2;
    }
    static int getSum(int n, int qs, int qe)
    {
        // Check for erroneous input values
        if (qs < 0 || qe > n - 1 || qs > qe) {
           // System.out.println("Invalid Input");
            return -1;
        }
        return getSumUtil(0, n - 1, qs, qe, 0);
    }
    static int getSumUtil(int ss, int se, int qs, int qe, int si)
    {
        // If segment of this node is a part of given range, then return
        // the sum of the segment
        if (qs <= ss && qe >= se)
            return st[si];
 
        // If segment of this node is outside the given range
        if (se < qs || ss > qe)
            return Integer.MAX_VALUE;
 
        // If a part of this segment overlaps with the given range
        int mid = getMid(ss, se);
        return Math.min(getSumUtil(ss, mid, qs, qe, 2 * si + 1) ,
                getSumUtil(mid + 1, se, qs, qe, 2 * si + 2));
    }
    static void updateValue(int arr[], int n, int i, int new_val)
    {
        // Check for erroneous input index
        if (i < 0 || i > n - 1) {
//            System.out.println("Invalid Input");
            return;
        }
 
        // Get the difference between new value and old value
        int diff = new_val - arr[i];
 
        // Update the value in array
        arr[i] = new_val;
 
        // Update the values of nodes in segment tree
        updateValueUtil(0, n - 1, i, diff, 0);
    }
    static void updateValueUtil(int ss, int se, int i, int diff, int si)
    {
        // Base Case: If the input index lies outside the range of
        // this segment
        if (i < ss || i > se)
            return;
 
        // If the input index is in range of this node, then update the
        // value of the node and its children
        st[si] = st[si] + diff;
        if (se != ss) {
            int mid = getMid(ss, se);
            updateValueUtil(ss, mid, i, diff, 2 * si + 1);
            updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
        }
    }
    static boolean checkbound(int x , int y , int m , int n){
        if(x<0 || x>=m || y<0 || y>=n)return false;
        return true;
    }
    static void printarr(int[][] a){
        int m = a.length , n = a[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }
    }
    static void printarr(int[] a){
        int n = a.length;
            for(int j=0;j<n;j++){
                System.out.print(a[j]+" ");
            }
            System.out.println();

        
    }

    static void revarr(int[] a ){
        int i=0,j=a.length-1;
        while(i<j){
            int tem = a[i];
            a[i]=a[j];
            a[j]=tem;
            i++;j--;
        }
        //return a;
    }
    
    
    static int[] st;
    static FastReader br=new FastReader();//(new InputStreamReader(System.in));
/*

*/
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        int t=1;
        br=new FastReader();
                t=br.ni();//Integer.parseInt(br.readLine().trim());
        StringBuilder sb=new StringBuilder();
         
        
    in1 :   while(t-->0)
        {
            
             //
              //      solve();
                sb.append(solve()+"\n");
        }
            //          System.out.println("OUTPUT:::");
    
        System.out.println(sb);
    }

    static int solve(){
        Stack<Character> st1 = new Stack<>();
        char[] a = br.ncarr();
        int n = a.length;
        for(int i=0;i<n;i++){
            if(st1.isEmpty()){
                st1.push(a[i]);

            }
            else {
                if(a[i]=='B')st1.pop();
                else st1.push(a[i]);
            }
        }
        return st1.size();

    }
        
    /*4 3 0 1 2 0
    1 0 0 0 0  
      1 0 0 0
            1
          1
        1
            1  

        */
    }

    
    



    
    
