题目描述

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

输入格式
本题包含多组测试数据。

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

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

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

样例
输入

3
8
00110100
10
1001000010
4
0000

输出

5
7
0

测试点一：第一天接种 $7$，第二天接种 $1$。
测试点二：第一天接种 $5$，第二天接种 $7$。
测试点三：没有疫情，不需要接种。

数据范围与提示
$1 \leq T \leq 100000$
$1 \leq n \leq 100000$
$\sum n \leq 10^6$