E. Anton Would Approve This Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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
Input
7
6
101101
6
001010
1
0
8
00101011
15
001101010101101
2
01
30
010110101010110101011010101101
Output
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$$$.