E. 长距离反转操作

每次测试的时间限制：3 秒
每次测试的内存限制：256 兆字节

题目描述

给定一个长度为 $n$ 的二进制字符串 $s$。二进制字符串是指只包含字符 '1' 和 '0' 的字符串。

你可以选择一个整数 $k$（$1 \le k \le n$），然后执行任意次以下操作：
选择字符串中连续的 $k$ 个字符，将它们全部反转，即把所有的 '0' 变成 '1'，所有的 '1' 变成 '0'。

通过这些操作，你需要使得字符串中的所有字符都变为 '1'。

例如，如果 $n = 5$，$s = \texttt{00100}$，你可以选择 $k = 3$，并按以下步骤操作：

1. 选择第 $1$ 到第 $3$ 个字符的子串，得到 $s = \texttt{11000}$；
2. 选择第 $3$ 到第 $5$ 个字符的子串，得到 $s = \texttt{11111}$。

请找出最大的 $k$，使得可以通过上述操作将字符串中的所有字符变为 '1'。注意，达到目标所需的操作次数不重要。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$）——字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，由字符 '1' 和 '0' 组成。

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

输出格式

对于每个测试用例，输出一个整数 $k$（$1 \le k \le n$），表示能够通过所述操作使字符串全变为 '1' 的最大 $k$。

示例

输入

5
5
00100
5
01000
7
1011101
3
000
2
10

输出

3
2
4
3
1