该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

洋红蒸汽

题目描述

你有一条长度为 $n$ 的数组（可视作一排格子），每个格子处于以下两种状态之一：

• 纯白水汽：用字符 '0' 表示
• 洋红蒸汽：用字符 '1' 表示

你拥有若干瓶汽水。每消耗 1 瓶汽水，你可以选择一个位置 $i$（$1 \le i \le n$），并将位置 $i$ 及其相邻的左右格子（若存在）一起变为 纯白水汽。

形式化地，这次操作会将下标集合

中的所有格子状态变为 '0'。

注意：汽水可以对任意状态的格子使用（无论该格子当前是 '0' 还是 '1'）。

你的目标是：通过若干次操作，使得数组中的所有格子最终都变为 '0'，并且 使用的汽水瓶数最少。请输出这个最小值。

输入格式

第一行包含一个正整数 $T$（$1 \le T \le 100$），表示测试数据组数。

对于每组测试数据：

• 第一行包含一个正整数 $n$（$1 \le n \le 1000$），表示数组长度。
• 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 '0' 和 '1' 组成，其中
  • '0' 表示纯白水汽
  • '1' 表示洋红蒸汽

输出格式

对于每组测试数据，输出一行一个整数，表示将所有格子变为 '0' 所需消耗汽水的最少瓶数。

输入输出样例 #1

输入 #1

4
5
00000
5
11111
7
1110101
15
010101010101010

输出 #1

0
2
2
4

说明/提示

• 每次操作会将一个格子及其左右相邻格子（最多共 $3$ 个位置；若在边界处则只作用于存在的格子）全部变为 '0'。
• 汽水可以对 '0' 或 '1' 的格子使用。

样例一：

$n=5,\ s=\texttt{00000}$：已经全为 '0'，不需要操作，答案为 $0$。

样例二：

$n=5,\ s=\texttt{11111}$： 例如在 $i=2$ 操作一次可将位置 $1,2,3$ 变为 '0'，再在 $i=4$ 操作一次可将位置 $3,4,5$ 变为 '0'，共 $2$ 次，答案为 $2$。

样例三：

$n=7,\ s=\texttt{1110101}$： 一种最优方案是分别在 $i=2,\ 6$ 进行操作，共 $2$ 次即可全部变为 '0'，答案为 $2$。

样例四：

$n=15,\ s=\texttt{010101010101010}$： 一种最优方案是分别在 $i=2,\ 5,\ 8,\ 11$ 进行操作，共 $4$ 次即可全部变为 '0'，答案为 $4$。