Problem Description

A certain country has $n$ cities. For all $1 \leq i < n$, city $i$ and city $i + 1$ are connected by a two-way road.

An epidemic breaks out in the country. In each city, either nobody is infected, or everyone is infected. Specifically, a city is infected initially if and only if $s_i = 1$.

The epidemic will spread. Every day, in the morning, you may vaccinate the residents of one uninfected city. In the afternoon, each infected city spreads to its neighboring cities. If a neighboring city has not been vaccinated, it will immediately become fully infected.

As the city manager, you want to know: under an optimal strategy, what is the minimum number of cities in which everyone becomes infected.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains an integer $n$.

The second line contains a string $s$ of length $n$.

Output Format

For each test case:

Output one line with an integer, representing the required value.

3
8
00110100
10
1001000010
4
0000

5
7
0

Hint

Sample #1 Explanation

Test case 1: Vaccinate city $7$ on the first day, and vaccinate city $1$ on the second day.

Test case 2: Vaccinate city $5$ on the first day, and vaccinate city $7$ on the second day.

Test case 3: There is no epidemic initially, so vaccination is not needed.

Constraints

For $100\%$ of the data, $1 \leq n, T \leq 10^5$, $1 \leq \sum n \leq 10^6$.

Translated by ChatGPT 5