给定一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串 $S$。 你可以对 $S$ 执行以下两种操作：

• 操作 1：选择一个连续子串 $010$，将其替换为 $1$。
• 操作 2：选择一个连续子串 $11$，将其替换为 $1$。

求你可以执行操作的最大次数。 你有 $T$ 组测试数据，请分别求解。

输入格式

输入通过标准输入给出，格式如下：

$T$ $\text{case}_1$ $\vdots$ $\text{case}_T$

每组测试数据的格式如下：

$N$ $S$

• $1 \le T \le 10^5$
• $1 \le N \le 10^6$
• $S$ 是一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串。
• 所有测试数据的 $N$ 之和不超过 $10^6$。
• $T$ 和 $N$ 均为整数。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

样例

样例输入 1

5
6
010100
4
0110
3
100
2
00
20
01001100000001101001

样例输出 1

3
2
0
0
11

说明

在第一组测试数据中，你可以按如下方式执行操作：

• 将 $010100$ 中带下划线的 $010$ 替换为 $1$，$S$ 变为 $0110$。
• 将 $0110$ 中带下划线的 $11$ 替换为 $1$，$S$ 变为 $010$。
• 将 $010$ 中带下划线的 $010$ 替换为 $1$，$S$ 变为 $1$。

你无法对 $S$ 执行超过三次操作，因此答案为 $3$。