拜托吉亚（Bajtocja）爆发了疫情！一种名为 SPLAY-CRT-2（俗称“克鲁斯卡尔病毒”）的病毒正在威胁公民的健康。幸运的是，拜托吉亚最聪明的头脑很快研发出了一种有效的疫苗。然而，问题并没有结束——现在需要规划疫苗接种工作。

拜托吉亚由 $n$ 个城市组成，编号从 $1$ 到 $n$。这些城市沿一条主干道分布，因此对于每个 $i$（$1 \le i \le n - 1$），编号为 $i$ 和 $i+1$ 的城市相邻。

每个城市最初要么完全没有病毒，要么所有居民都已感染。每天，拜托吉亚卫生部门可以为任意一个尚未被病毒占领的城市的所有居民接种疫苗。不幸的是，每天晚上，每个尚未接种疫苗、此前未感染但与已感染城市相邻的城市，都会被病毒占领。拜托吉亚的疫苗接种过程在清晨开始：首先卫生部门可以为一个城市接种疫苗，然后病毒才开始传播。

你的任务是规划疫苗接种，使得当拜托吉亚的疫情稳定时（即每个城市要么被病毒感染，要么已接种疫苗），被感染的城市数量尽可能少。

请帮助拜托吉亚的居民，计算在最优接种策略下，会有多少个城市被感染。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。

接下来的 $2t$ 行包含各测试用例的描述。每个用例包含两行：第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示拜托吉亚的城市数量。第二行包含一个长度为 $n$ 的由 $0$ 和 $1$ 组成的字符串。如果第 $i$ 个字符为 $1$，则第 $i$ 个城市最初被感染；否则，该城市最初未感染。

所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

输出应包含 $t$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 个测试用例中被感染城市的最少数量。

样例

样例输入 1

3
8
00110100
10
1001000010
4
0000

样例输出 1

5
7
0

说明

在第一个测试用例中，我们可以先为第二个城市接种疫苗。夜间，病毒会传播到城市 $5$ 和 $7$。第二天，我们可以为第八个城市接种疫苗。此时疫情已得到控制。剩下的只需为城市 $1$ 接种疫苗。这样，共有 $5$ 个城市（编号为 $3, 4, 5, 6$ 和 $7$）会被感染。可以证明这是最优结果。

在第二个测试用例中，我们可以按 $8, 6, 7$ 的顺序为城市接种疫苗。

在最后一个测试用例中，拜托吉亚根本没有病毒，因此可以按任意顺序为所有城市接种疫苗。*

*你可能在想，既然根本没有病毒，为什么要给拜托吉亚的居民接种疫苗。但不能排除未来病毒会从其他国家传入的可能性，因此预防性地照顾公民的健康是值得的。