CANDYSTRIPE

We have $N$ chocolates arranged in a row, each wrapped and placed in a film. Some of these chocolates are bitter ("$B$") and some are sweet ("$S$"). For example, the string "$BSBSSB$" represents a film consisting of $6$ chocolates, where the first one is bitter, the second one is sweet, and so on.

Our two-year-old brother naturally prefers sweet chocolates. He won't complain if he eats any bitter chocolates as well. However, if at any moment he has eaten more bitter chocolates than sweet ones, he will burst into tears, and of course, we don't want to upset him.

We want to give our brother a contiguous segment of the original film, possibly by trimming from the beginning and/or the end. Our brother will start eating the chocolates one by one in order until they are finished, but we don't know from which end of the segment he will start.

Find the length of the longest segment of the original film that we can give to our brother, ensuring that he won't burst into tears.

Input:

The first line of the input will contain a positive integer $T$: the number of initial films for which you need to find the solution. Each of the next $T$ lines will correspond to an initial film and will contain a string consisting of characters "$B$" and "$S$".

Output:

The output should contain $T$ lines, each line containing exactly one integer: the answer to the above problem for the corresponding initial film.

Constraints:

• $1\le T\le 10$.
• The length of each film will be $1\le N\le 1.000.000$.
• The total length of all films in each test case will not exceed $2.000.000$.
• Time Limit: $1$ sec.
• Memory Limit: $64$ MB.
• For test cases with a total value of $20$, it will be $1\le N\le 1000$.
• For test cases with a total value of $50$, it will be $1\le N\le 10.000$.

Example of Input - Ouput:

input

5
BSBSSB
SSBBSS
SBSBSBBSSS
SSSBBSBSBSBBB
ΒΒΒΒ

output

4
6
5
5
0

Explanation of the example:

For the first film, the longest segment we can give to our brother is "$SBSS$", which results from cutting off the two bitter chocolates at both ends. For the second film, we can give him the entire film. For the third film, the longest segment we can give him is the prefix "$SBSBS$". The same applies to the fourth film, where the segment "$SBSBS$" results from cutting the first five and the last three chocolates. Finally, for the fifth film, there is no segment that we can give to our brother that would make him happy since there are no sweet chocolates.