409177: GYM103449 E Rubik String

E. Rubik Stringtime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard output

The Rubik's cube is a 3-D combination puzzle created by Hungarian sculptor and proffesor of architecture Erno Rubik. On the original classic Rubik's Cube, each of the six faces was covered by nine stickers, each of one of six solid colours: white, red, blue, orange, green, and yellow. In models as of 1988, white is opposite yellow, blue is opposite green, and orange is opposite red. - excerpt from Wikipedia

You are given a string $$$s$$$ of $$$n$$$ characters $$$s_i \in \{W, R, B, O, G, Y\}$$$. Each of these 6 letters coresponds to a colour featured on the Rubik's Cube (White, Red, Blue, Orange, Green and Yellow, respectively).

$$$s$$$ is considered a Rubik String if, for all adjacent characters, their coresponding colours are adjacent faces of the Rubik's Cube. For example, $$$"WRBOGY"$$$ is a Rubik String, while $$$"WW"$$$ and $$$"WYO"$$$ are not.

Naturally, not all strings are Rubik Strings, but they can be transformed into one via a sequence of (hopefully harmless) operations. In one operation, one can turn any character in $$$s$$$ into any other character $$$c_2 \in \{W, R, B, O, G, Y\}$$$.

For a given string $$$s$$$, find the minimum amount of operations required to make $$$s$$$ a Rubik String.

Input

Each test contains multiple testcases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The following lines will contain the descriptions of the test cases.

The description of each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of string $$$s$$$.

The second line contains $$$n$$$ characters — the elements of string $$$s$$$.

It is guaranteed that the sum of $$$n$$$ will not exceed $$$5 \cdot 10^5$$$.Output

For each testcase print one integer — the minimum amount of operations required to turn $$$s$$$ into a Rubik String.

Scoring

• Subtask 1 (20 points): $$$s_i \in \{W,Y\}, \forall i \in [1,n]$$$;
• Subtask 2 (30 points): $$$s_i \in \{W,R,B\}, \forall i \in [1,n]$$$;
• Subtask 3 (50 points): No further constraints.

ExampleInput

5
7
WWWWWWW
6
WRBOGY
2
WW
3
WYO
10
WYYWWBGROB

Output

3
0
1
1
4

Note

• In the first testcase, minimum number of operations needed to transform $$$s$$$ into a Rubik String is $$$3$$$. One such Rubik String is $$$s="WRWOWBW"$$$;
• In the second testcase, $$$s$$$ is already a Rubik String;
• In the third testcase, an example of a Rubik String obtainable in one operation is $$$s="BW"$$$;
• In the fourth testcase, an example of a Rubik String obtainable in one operation is $$$s="WGO"$$$;
• In the fifth testcase, an example of a Rubik String obtainable in four operations is $$$s="WGYOWBYRWB"$$$;