Minimum Changes to Form a Valid Path

You are given a series of crossroads arranged in a line. Each crossroad is either green (G) or red (R). You must determine the minimum number of crossroads whose state needs to be changed from red to green so that there exists at least one contiguous path (i.e. a sequence of adjacent crossroads) from the first crossroad to the last crossroad.

Note: It is guaranteed that in each test case, the first and the last crossroads are already green.

Observation: If we view the crossroads string and split it by 'G', we obtain segments of consecutive red crossroads. Let \(k\) be the number of non-empty segments. Then, if \(k > 1\), the minimum number of changes required is \(k-1\); otherwise, if \(k \le 1\), no changes are needed. The answer for each test case is computed as:

[ ans = \begin{cases} k-1 & \text{if } k > 1,\ 0 & \text{if } k \le 1. \end{cases} ]

For example, consider the crossroads string "GRGRG". Splitting by 'G' gives tokens: "", "R", "R", "". There are two non-empty segments (i.e. \(k=2\)), hence the minimum changes required is \(2-1=1\).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \(T\), the number of test cases.
• For each test case, there are two lines:
• The first line contains an integer \(N\) representing the number of crossroads.
• The second line contains a string of length \(N\) consisting only of the characters 'G' (Green) and 'R' (Red).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of changes required to guarantee a contiguous green path from the first to the last crossroad.

## sample

3
5
GRGRG
4
GGGG
6
GRRGRG

1
0
1

</p>