All Tracks Problem

Xenny and Classroom
Tag(s):

Ad-Hoc, Easy

Problem
Editorial
Analytics

Xenny was a teacher and his class consisted of N boys and N girls. He took all his students to the playground and asked them to stand in a straight line. The boys and the girls formed a perfect line, but Xenny seemed unhappy. He wanted them to form an alternating sequence of boys and girls, i.e., he wanted that after a boy, there should be a girl in the line, and vice-versa.

In order to form an alternating sequence, a boy and a girl could swap their positions.

Given the original sequence in which the boys and girls were standing, find the minimum number of swaps required to form an alternating sequence.

Note: An alternating sequence can start either with a boy or a girl.

Input

First line of input consists of a natural number T - the number of testcases.
T testcases follow. For each testcase:

First line consists of a single integer N - the number of boys, and the number of girls.
Second line consists of a string of length \(2N\), representing the original sequence.
In this string, a boy is represented by uppercase character B and a girl by G.

Output

For each testcase, print the minimum number of swaps required to get an alternating sequence on a new line.

Constraints

\(1 \le T \le 5\)

\(1 \le N \le 10^6\)

Subtasks

  1. \(1 \le N \le 20\) : 10 points
  2. \(1 \le N \le 10^6\) : 90 points
SAMPLE INPUT
1
2
BBGG
SAMPLE OUTPUT
1
Explanation

The first boy from left can swap his position with the first girl from right to get the sequence:

GBGB

This is an alternating sequence and it was obtained using 1 swap.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

May Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?