JB 正在玩一个游戏。游戏中有 $n$ 座城市，编号为 $1, 2, \dots, n$。第 $i$ 座城市和第 $j$ 座城市相邻，当且仅当 $i = j - 1$ 或 $i = j + 1$。最初，有一些城市被 JB 占领。

游戏按轮次进行。在每一轮开始时，每个被占领的城市最多可以标记一个相邻的未被占领的城市作为攻击目标。在这一轮结束时，所有被标记的攻击目标都变为被占领状态。当所有城市都被占领时，游戏结束。

JB 希望在最少的轮次内占领所有城市。你能帮帮他吗？

输入格式

输入包含多组测试数据。第一行包含一个正整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示城市的数量。

第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 仅包含字符 '0' 和 '1'。第 $i$ 个字符描述了第 $i$ 座城市的初始状态：如果 $s_i = \text{'1'}$，则第 $i$ 座城市最初被 JB 占领。否则，第 $i$ 座城市最初未被占领。

保证所有测试数据的 $n$ 之和不超过 $10^6$。同时保证 $s$ 中至少包含一个 '1'。

输出格式

对于每组测试数据，输出一行，包含占领所有城市所需的最少轮次。

样例

输入格式 1

5
3
010
4
0100
7
0001000
5
11111
6
010101

输出格式 1

1
2
3
0
1

说明

对于第二个测试用例，最优方案是 $0100 \to 0110 \to 1111$。