Mr. Seth loves his friend A(secret). Recently he forgot to gift her on her day that made "A" very upset.
Mr. Seth tried many things to make 'A' very happy and told her that he will not repeat the mistake and forgive him. Finally, "A", asked Mr. Seth to prove his love by giving him a task
The task is :
Now 'A' gave him string str which only has characters 'A' and 'G' only. Now "A", asks the maximum number of A's in the given string. But there's a condition that you can choose a substring of range [l,r].
where 1<=l<=r<=length(str).
And flip the ranged characters i.e. range [l,r]. If a character is 'A' then change it to 'G' and vice versa.
As Mr. Seth loves "A" very much and he does not want to make her upset. Help her to prove his love.
NOTE: It is necessary for Mr. Seth to choose a segment.
Input :
- The first line is T (Number of Test Cases)
- Next T lines contain a String.
Output :
print T lines with a maximum number of A's.
CONSTRAINTS:
1 ≤ T ≤ 10
1 ≤ length(str) ≤ 105
for test case 1 optimal substring is from [2,3] and string will become AAAAG and so the number of A's in it is 4.
similarly for test case 2 optimal substring is from [2,3] and string will become AAAA .
And for test case 3 optimal substring is from [3,3] and string will become AAAAA.
