Beautiful String Replacements

A string is called beautiful if no two adjacent characters are the same.

You are given a string s of length n consisting of lowercase English letters. You can replace any character in the string with any other lowercase letter as many times as needed. The goal is to transform the string into a beautiful string with the minimum number of replacements.

Hint: For a segment of consecutive identical characters of length L, the minimum number of replacements needed is \(\lfloor L/2 \rfloor\).

Example: For s = "aabb", you can change it to "abab" with 2 replacements.

inputFormat

The first line of input contains an integer t, denoting the number of test cases. Each test case consists of two lines: the first line contains an integer n (the length of the string), and the second line contains the string s.

All input is to be read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line: the minimum number of replacements needed to make the string beautiful.

All output should be written to standard output (stdout).

## sample

3
4
aabb
5
ababa
3
aaa

2
0
1

</p>