C. 左右房屋

每个测试用例时间限制：$2$ 秒 每个测试用例内存限制：$256$ 兆字节

在 Letovo 村有 $n$ 栋房屋。村民们打算修建一条大路，将村庄分成左右两侧。 每位居民都希望住在街道的左侧或右侧，用序列 $a_1,a_2,\dots,a_n$ 表示：

• $a_j=0$ 表示第 $j$ 栋房屋的居民希望住在街道左侧；
• $a_j=1$ 表示希望住在街道右侧。

道路会建在两栋房屋之间。道路左边的房屋划为左侧，右边的房屋划为右侧。 更形式化地说：设道路建在房屋 $i$ 和 $i+1$ 之间，则：

• 位置在 $1$ 到 $i$ 的房屋在街道左侧；
• 位置在 $i+1$ 到 $n$ 的房屋在街道右侧。

道路也可以建在第一栋房屋之前（此时全村都在右侧）或最后一栋房屋之后（全村都在左侧），对应 $i=0$ 与 $i=n$。

为了规划公平，决定按照如下要求修路： 道路两侧中，每一侧至少有一半居民对自己所在的一侧满意。 形式化地说：某一侧有 $x$ 位居民，则至少要有 $\lceil\frac{x}{2}\rceil$ 位居民希望住在这一侧（$\lceil x\rceil$ 表示对实数 $x$ 向上取整）。

具体要求：

• 道路左侧共有 $i$ 栋房屋，其中 $a_j=0$ 的数量至少为 $\lceil\frac{i}{2}\rceil$；
• 道路右侧共有 $n-i$ 栋房屋，其中 $a_j=1$ 的数量至少为 $\lceil\frac{n-i}{2}\rceil$。

请你确定，应该在第 $i$ 栋房屋之后修建道路，满足上述条件，并且尽可能靠近村庄正中间。 形式化地说：在所有合法位置 $i$ 中，最小化 $|\frac{n}{2}-i|$。 如果有多个 $i$ 同时取到最小距离，输出较小的那个。

输入格式

输入包含多组测试用例。 第一行一个整数 $t$（$1\le t\le 2\cdot 10^4$）—— 测试用例数量。

每组测试用例：

• 第一行一个整数 $n$（$3\le n\le 3\cdot 10^5$）；
• 第二行一个长度为 $n$、仅由字符 $0$ 和 $1$ 构成的字符串 $a$。

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

输出格式

对每组测试用例，输出一个整数 $i$ —— 表示在第 $i$ 栋房屋之后修路。 （若修在第一栋房屋前，输出 $0$。） 题目保证解一定存在。

样例输入

7
3
101
6
010111
6
011001
3
000
3
110
3
001
4
1100

样例输出

2
3
2
3
0
1
0

样例说明

以第一个样例为例：

如果在第 $1$ 栋房屋后修路，左侧有 $1$ 栋房屋 $a_1=1$，居民希望住在右侧。左侧满意人数为 $0$，不满足至少 $\lceil\frac{1}{2}\rceil=1$ 人的要求，因此不合法。

如果在第 $2$ 栋房屋后修路：

• 左侧 $2$ 人（$a_1=1,a_2=0$），满意人数为 $1$，满足 $\lceil\frac{2}{2}\rceil=1$；
• 右侧 $1$ 人（$a_3=1$），满意人数为 $1$，满足 $\lceil\frac{1}{2}\rceil=1$。

因此该位置合法，且是最优解。