P9046 [PA 2021] Pandemia

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

**本题有多组测试数据。** 第一行一个整数 $T$，表示数据组数。 对于每组数据： 第一行，一个整数 $n$； 第二行，一个长度为 $n$ 的字符串 $s$。

对于每组数据： 一行，一个整数，表示所求的值。

#### 样例 #1 解释 测试点一：第一天接种城市 $7$，第二天接种城市 $1$。 测试点二：第一天接种城市 $5$，第二天接种城市 $7$。 测试点三：初始不存在疫情，因此不需要接种。 #### 数据范围 对于 $100\%$ 的数据，$1 \leq n, T \leq 10^5$，$1 \leq \sum n \leq 10^6$。