311178: CF1945C. Left and Right Houses

C. Left and Right Housestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

In the village of Letovo, there are $n$ houses. The villagers decided to build a big road that will divide the village into left and right sides. Each resident wants to live on either the right or the left side of the street, which is described as a sequence $a_1, a_2, \dots, a_n$, where $a_j = 0$ if the resident of the $j$-th house wants to live on the left side of the street; otherwise, $a_j = 1$.

The road will pass between two houses. The houses to the left of it will be declared the left-side, and the houses to the right will be declared the right-side. More formally, let the road pass between houses $i$ and $i+1$. Then the houses at positions between $1$ and $i$ will be on the left side of the street, and at positions between $i+1$ and $n$ will be on the right side. The road also may pass before the first and after the last house; in this case, the entire village is declared to be either the right or left side, respectively.

To make the design fair, it was decided to lay the road so that at least half of the residents on each side of the village are satisfied with the choice. That is, among $x$ residents on one side, at least $\lceil\frac{x}{2}\rceil$ should want to live on that side, where $\lceil x \rceil$ denotes rounding up a real number $x$.

To the left of the road, there will be $i$ houses, among the corresponding $a_j$ there must be at least $\lceil\frac{i}{2}\rceil$ zeros. To the right of the road, there will be $n-i$ houses, among the corresponding $a_j$ there must be at least $\lceil\frac{n-i}{2}\rceil$ ones.

Determine after which house $i$ the road should be laid in order to satisfy the described condition and be as close to the middle of the village as possible. Formally, among all suitable positions $i$, minimize $\left|\frac{n}{2} - i\right|$.

If there are multiple suitable positions $i$ with the minimum $\left|\frac{n}{2} - i\right|$, output the smaller one.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2\cdot 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 3\cdot 10^5$). The next line of each test case contains a string $a$ of length $n$, consisting only of $0$ and $1$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

Output

For each test case, output a single number $i$ — the position of the house after which the road should be laid (if it should be laid before the first house, output $0$). We can show that the answer always exists.

ExampleInput

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

Output

2
3
2
3
0
1
0

Note

Let's consider the first example of input data.

If we lay the road after the first house, there will be one house $a_1 = 1$ on the left side of the street, the resident of which would like to live on the right side of the street. Then $0$ out of $1$ residents on the even side will be satisfied with the choice, which means that the road cannot be laid after house $1$.

If we lay the road after the second house, $1$ out of $2$ residents on the left side (with preferences $a_1 = 1$, $a_2 = 0$) and $1$ out of $1$ resident on the right side (with preference $a_3 = 1$) will be satisfied with the choice. More than half of the residents on each side are satisfied with the choice, which means that the road can be laid after house $2$. We can show that this is the optimal answer.

题目大意：
在Letovo村有n座房子，村民决定建一条大路将村子分为左右两边。每个居民都想住在街道的左边或右边，用序列a_1, a_2, ..., a_n表示，如果第j个房子的居民想住在街道左边，则a_j = 0；否则，a_j = 1。道路将位于两座房子之间，将位于其左侧的房子声明为左侧行，位于其右侧的房子声明为右侧行。为了使设计公平，决定将道路铺设得使每个村庄侧至少有一半的居民对选择感到满意。即在某一侧的x个居民中，至少有⌈x/2⌉个居民想住在那一侧，其中⌈x⌉表示将实数x向上取整。

输入输出数据格式：
每个测试包含多个测试案例。第一行包含测试案例数t (1 ≤ t ≤ 2*10^4)。接下来是每个测试案例的描述。
每个测试案例的第一行包含一个整数n (3 ≤ n ≤ 3*10^5)。下一行包含一个长度为n的字符串a，由0和1组成。
保证所有测试案例的n之和不超过3*10^5。

对于每个测试案例，输出一个数字i——道路应该铺设的房子位置（如果应该铺设在第一座房子之前，输出0）。可以证明答案总是存在的。题目大意： 在Letovo村有n座房子，村民决定建一条大路将村子分为左右两边。每个居民都想住在街道的左边或右边，用序列a_1, a_2, ..., a_n表示，如果第j个房子的居民想住在街道左边，则a_j = 0；否则，a_j = 1。道路将位于两座房子之间，将位于其左侧的房子声明为左侧行，位于其右侧的房子声明为右侧行。为了使设计公平，决定将道路铺设得使每个村庄侧至少有一半的居民对选择感到满意。即在某一侧的x个居民中，至少有⌈x/2⌉个居民想住在那一侧，其中⌈x⌉表示将实数x向上取整。 输入输出数据格式： 每个测试包含多个测试案例。第一行包含测试案例数t (1 ≤ t ≤ 2*10^4)。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数n (3 ≤ n ≤ 3*10^5)。下一行包含一个长度为n的字符串a，由0和1组成。 保证所有测试案例的n之和不超过3*10^5。 对于每个测试案例，输出一个数字i——道路应该铺设的房子位置（如果应该铺设在第一座房子之前，输出0）。可以证明答案总是存在的。