为了获得 99.1% 的纯度，实验室里的每样东西每天都必须彻底清洁。现在，Jesse 正准备清理一个放书的架子。

架子上有 $n$ 个放书的位置。架子上放置了一些书（可能没有）。如果某个位置是空的，Jesse 可以直接清洁它，无需消耗任何能量（他非常擅长清洁）。他不能清洁当前有书的位置。如果某个位置有书，且相邻的位置是空的，Jesse 可以将书移动到那个相邻的位置，消耗 1 点能量。

Jesse 是一个非常忙碌的人，他不想花费太多的能量。对于每个测试用例，请计算 Jesse 所需花费的最小能量。

输入格式

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

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示架子上的位置数量。

第二行包含一个长度为 $n$ 的字符串 $s$，其中如果第 $i$ 个位置没有书，则 $s_i = 0$，否则 $s_i = 1$。

保证在所有提供的测试用例中，架子总是可以被清理干净的。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

输出 $t$ 行，每行包含一个整数，表示 Jesse 所需花费的最小能量。

样例

输入 1

3
2
01
5
00110
9
101010101

输出 1

1
2
6

说明

在第一个测试用例中，Jesse 可以先清洁第一个位置，然后将书从第二个位置移动到第一个位置（消耗 1 点能量），最后清洁第二个位置。