A string is called as ab string if it is in the form of $a^i b^j a^k$  or $b^i a^k b^k$  where $i>=0 , j>=0 , k>=0$ .

Now you are given a string consisting of only 'a' and 'b' in it.You are allowed to remove any number of characters from this string (possibly 0). You need to find the maximum possible size of ab string can be obtained.

Input :

• First line of input contains an integer T dentoing no of test cases.
• Next T lines will be given a string.

Output :

For each test case output maximum possible size of ab string that can be obtained in a new line.

Constraints :

$1<=T<=100$

$1<=|S|<=10^6$