You are given a row of n tokens in a row colored red and blue.
In one move, you can choose to perform a capture. A capture chooses a token, and makes a jump over exactly one other token, and removes a token of the opposite color.
More specifically, given three adjacent tokens we can convert it into the following state with two adjacent tokens:
Given the initial row of tokens, return the minimum possible length of the resulting row after a series of captures.
Input Format:
The first line will contain the number of test cases T.
Each test case can be described with one line.
This line will contain a string consisting of only characters 'R' and 'B' denoting the colors in the row.
Output Format:
Output T numbers, the answers to each problem.
Constraints
There is no partial credit for this problem.
There is only one file for this problem. The file has the following constraints.
In the first sample, there are no possible captures we can perform.
In the second sample, we can perform a capture with the red token to get the state .
In the third sample, we can apply the following captures . The hat denotes which token is doing the capture in the next step.
For the fourth sample, we can't do any captures.
