P9046 [PA 2021] Pandemia

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.

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

For each test case: Output one line with an integer, representing the required value.

#### 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