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$.