Gurpreet loves his crush A(secret) very much.
Recently he forgot her birthday that made "A" very upset.
Gurpreet tried lot to make her happy and asked her to forgive him once. Finally "A" changed her mood and gave Gurpreet a task to prove his love.
The task is :
Given a string str consisting of characters 'A' and 'G' only. Now "A" asks the maximum number of A's in the given string. But there's a twist you have to choose a substring of range [l,r].
where 1<=l<=r<=length(str).
And flip all the characters in choosen range [l,r]. If character is 'A' then change it to 'G' and if it is 'G' then change it to 'A'.
As Gurpreet loves "A" very much so he does not want to make her upset again. Help him with maximum A's.
NOTE:It is necessary for Gurpreet to choose a segment.
input :
first line is T (Number of Test Cases)
Next T lines contain a String.
output :
print T lines with 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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor