Pair Deletion - Repovive Premier Round 7 | Repovive

20A. Pair Deletion

500 pts1s256 MB

There are $2n$ balls in a row. Exactly $n$ of them are blue, and the other $n$ are red.

In one operation, you may choose a red ball and a blue ball somewhere to its right, then remove both of them. The relative order of all remaining balls does not change.

Find the minimum number of operations required so that no red ball has a blue ball to its right. Equivalently, all remaining blue balls must be to the left of all remaining red balls.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 10^5$
$|s| = 2n$
$s$ contains exactly $n$ characters B and exactly $n$ characters R.
The sum of $n$ over all test cases does not exceed $10^5$ .

Input

t

\left. \begin{array}{l} n \\ s \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

1
BR

Case 2

1
RB

Case 3

3
BRBRBR

Case 4

4
RBBRBRRB

Case 5

5
RRBBRBBRRB

Explanation

Case 1

All blue balls are already to the left of all red balls, so no operation is needed.

Case 2

Remove the first ball and the second ball. No balls remain, so the required condition is satisfied.

Case 3

Remove the second ball and the fifth ball. The remaining row is BBRR.

Case 4

First, remove the first ball and the fifth ball, changing the row to BBRRRB. Then remove the third ball and the sixth ball. The remaining row is BBRR. No single operation is sufficient.

Case 5

First, remove the first ball and the sixth ball, changing the row to RBBRBRRB. Next, remove the first ball and the fifth ball, changing it to BBRRRB. Finally, remove the third ball and the sixth ball. The remaining row is BBRR. No sequence of only two operations is sufficient.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

There are $2n$ balls in a row. Exactly $n$ of them are blue, and the other $n$ are red.

In one operation, you may choose a red ball and a blue ball somewhere to its right, then remove both of them. The relative order of all remaining balls does not change.

Find the minimum number of operations required so that no red ball has a blue ball to its right. Equivalently, all remaining blue balls must be to the left of all remaining red balls.

$1 \le t \le 10^4$
$1 \le n \le 10^5$
$|s| = 2n$
$s$ contains exactly $n$ characters B and exactly $n$ characters R.
The sum of $n$ over all test cases does not exceed $10^5$ .

t

\left. \begin{array}{l} n \\ s \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

20A. Pair Deletion

Constraints

Input

Output

Samples

20A. Pair Deletion

Constraints

Input

Output

Samples