题目描述

某国有 $n$ 座城市，其中 $\forall 1 \leq i < n$，城市 $i$ 与城市 $i + 1$ 有双向道路相连。

该国发生了疫情，一个城市要么无人感染，要么全体感染。具体地，一个城市初始时被感染当且仅当 $s_i = 1$。

疫情会扩散，每一天上午，你可以为一个未感染的城市的居民接种疫苗，下午，每个被感染的城市会向相邻的城市扩散，如果相邻的城市未接种疫苗，它将立即全员感染。

你作为城市管理者，想要知道执行最优策略的情况下，最少会有几个城市的所有人都被感染。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行，一个整数 $n$；

第二行，一个长度为 $n$ 的字符串 $s$。

输出格式

对于每组数据：

一行，一个整数，表示所求的值。

3
8
00110100
10
1001000010
4
0000

5
7
0

提示

样例 #1 解释

测试点一：第一天接种城市 $7$，第二天接种城市 $1$。

测试点二：第一天接种城市 $5$，第二天接种城市 $7$。

测试点三：初始不存在疫情，因此不需要接种。

数据范围

对于 $100\%$ 的数据，$1 \leq n, T \leq 10^5$，$1 \leq \sum n \leq 10^6$。