Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Reverse Binary Strings

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a string $$$s$$$ of even length $$$n$$$. String $$$s$$$ is binary, in other words, consists only of 0's and 1's.

String $$$s$$$ has exactly $$$\frac{n}{2}$$$ zeroes and $$$\frac{n}{2}$$$ ones ($$$n$$$ is even).

In one operation you can reverse any substring of $$$s$$$. A substring of a string is a contiguous subsequence of that string.

What is the minimum number of operations you need to make string $$$s$$$ alternating? A string is alternating if $$$s_i \neq s_{i + 1}$$$ for all $$$i$$$. There are two types of alternating strings in general: 01010101... or 10101010...

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$; $$$n$$$ is even) — the length of string $$$s$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ ($$$s_i \in$$$ {0, 1}). String $$$s$$$ has exactly $$$\frac{n}{2}$$$ zeroes and $$$\frac{n}{2}$$$ ones.

It's guaranteed that the total sum of $$$n$$$ over test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print the minimum number of operations to make $$$s$$$ alternating.

Example

Input

3 2 10 4 0110 8 11101000

Output

0 1 2

Note

In the first test case, string 10 is already alternating.

In the second test case, we can, for example, reverse the last two elements of $$$s$$$ and get: 0110 $$$\rightarrow$$$ 0101.

In the third test case, we can, for example, make the following two operations:

- 11101000 $$$\rightarrow$$$ 10101100;
- 10101100 $$$\rightarrow$$$ 10101010.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2021 08:18:44 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|