311245: CF1955E. Long Inversions

E. Long Inversionstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A binary string $s$ of length $n$ is given. A binary string is a string consisting only of the characters '1' and '0'.

You can choose an integer $k$ ($1 \le k \le n$) and then apply the following operation any number of times: choose $k$ consecutive characters of the string and invert them, i.e., replace all '0' with '1' and vice versa.

Using these operations, you need to make all the characters in the string equal to '1'.

For example, if $n=5$, $s=00100$, you can choose $k=3$ and proceed as follows:

• choose the substring from the $1$-st to the $3$-rd character and obtain $s=\color{blue}{110}00$;
• choose the substring from the $3$-rd to the $5$-th character and obtain $s=11\color{blue}{111}$;

Find the maximum value of $k$ for which it is possible to make all the characters in the string equal to '1' using the described operations. Note that the number of operations required to achieve this is not important.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 5000$) — the length of the string $s$.

The second line of each test case contains a string $s$ of length $n$, consisting of the characters '1' and '0'.

It is guaranteed that the sum of the values $n^2$ over all test cases in the test does not exceed $25 \cdot 10^6$.

Output

For each test case, output the maximum integer $k$ ($1 \le k \le n$) for which it is possible to obtain a string $s$ consisting only of the characters '1' using the described operations.

ExampleInput

5
5
00100
5
01000
7
1011101
3
000
2
10

Output

3
2
4
3
1

题目大意：
给定一个长度为n的二进制字符串s（只包含字符'1'和'0'）。可以选择一个整数k（1≤k≤n），并对字符串中的任意k个连续字符进行反转（即，将所有的'0'变为'1'，将所有的'1'变为'0'）。使用这些操作，需要使字符串中的所有字符都变为'1'。求最大的k值，使得可以通过上述操作将字符串中的所有字符变为'1'。注意，达到目标所需的操作次数并不重要。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤5000）——字符串s的长度。
每个测试用例的第二行包含一个长度为n的字符串s，由字符'1'和'0'组成。
保证所有测试用例中n^2的和不超过25×10^6。

输出数据格式：
对于每个测试用例，输出可以使字符串s仅由字符'1'组成的最大整数k（1≤k≤n）。

示例：
输入：
5
5
00100
5
01000
7
1011101
3
000
2
10

输出：
3
2
4
3
1题目大意： 给定一个长度为n的二进制字符串s（只包含字符'1'和'0'）。可以选择一个整数k（1≤k≤n），并对字符串中的任意k个连续字符进行反转（即，将所有的'0'变为'1'，将所有的'1'变为'0'）。使用这些操作，需要使字符串中的所有字符都变为'1'。求最大的k值，使得可以通过上述操作将字符串中的所有字符变为'1'。注意，达到目标所需的操作次数并不重要。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤5000）——字符串s的长度。 每个测试用例的第二行包含一个长度为n的字符串s，由字符'1'和'0'组成。 保证所有测试用例中n^2的和不超过25×10^6。 输出数据格式： 对于每个测试用例，输出可以使字符串s仅由字符'1'组成的最大整数k（1≤k≤n）。 示例： 输入： 5 5 00100 5 01000 7 1011101 3 000 2 10 输出： 3 2 4 3 1