题目描述

题目译自 PA 2021 Runda 2 Pandemia

某国有 $n$ 座城市，其中 $i$ 与 $i + 1$ 有道路相连。
该国发生了疫情，一个城市要么无人感染，要么全体感染。具体来说，一个城市初始时被感染当且仅当 $s_i=1$。
疫情会扩散，每一天上午，你可以为一个未感染的城市的居民接种疫苗，下午，每个被感染的城市会向相邻的城市扩散，如果相邻的城市未接种疫苗，它将立即全员感染。
你作为城市管理者，想要知道最优策略下，最少几个城市被感染。

输入格式

本题包含多组测试数据。

第一行一个整数 $T$ ，表示测试点组数。

对于每组测试数据，第一行一个正整数 $n$，表示城市个数，第二行一个长度为 $n$ 的字符串 $s$。

输出格式

共 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案。

3
8
00110100
10
1001000010
4
0000

5
7
0

数据范围与提示

$1 \leq T \leq 100000$

$1 \leq n \leq 100000$

$\sum n \leq 10 ^ 6$