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:
- \(RxB \to xR\)
- \(BxR \to xB\)
- \(RxB \to Bx\)
- \(BxR \to Rx\)
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.
\(T = 1000\)
\(1 ≤ n ≤ 50\)
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 \(BR\).
In the third sample, we can apply the following captures \(BB\hat{R}RB \to \hat{B}BRR \to BB\hat{R} \to RB\). The hat denotes which token is doing the capture in the next step.
For the fourth sample, we can't do any captures.
