You are given a binary string of length $n$. A binary string is considered `good`

if none of its substrings are equal to `101`

or `010`

.

What is the smallest number of characters that need to be deleted from the given string in order to make it `good`

?

## Input

Each test contains multiple testcases. The first line of input contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the given string.

The second line of each testcase contains a binary string $\overline{s_1s_2\ldots s_n}$ ($s_i \in \{'0','1'\}$).

It is guaranteed that the sum of $n$ across all testcases does not exceed $3 \cdot 10^5$.

## Output

For each testcase, print smallest number of characters that need to be deleted from the given string in order to make it `good`

.

## Example

`stdin`

```
7
6
101101
6
001010
1
0
8
00101011
15
001101010101101
2
01
30
010110101010110101011010101101
```

`stdout`

```
2
1
0
2
4
0
9
```

### Note

In the first testcase, after deleting the second and fifth characters, $s$ will become $1111$.

In the second testcase, after deleting the fourth character, $s$ will become $00110$.

In the third testcase, we don't need to delete any characters.

In the fourth testcase, after deleting the third and fifth characters, $s$ will become $000011$.