长区间翻转

时间限制：3s
空间限制：256MB

题目描述

给定一个长度为 $n$ 的字符串 $s$，其中只包含字符 0 和 1。

你需要先选定一个整数 $k$，满足 $1\le k\le n$。此后可以执行任意次操作，每次选择连续的 $k$ 个字符，将其中的 0 变成 1，将 1 变成 0。所有操作使用相同的 $k$，也可以不执行任何操作。

求能够使整个字符串变成全 1 的最大的 $k$。

输入格式

第一行包含一个整数 $t$，表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$。

第二行包含一个长度为 $n$ 的字符串 $s$。

输出格式

对于每组测试数据，输出一个整数，表示满足要求的最大的 $k$。

样例输入 1

5
5
00100
5
01000
7
1011101
3
000
2
10

样例输出 1

3
2
4
3
1

提示

第一组测试数据可以选择 $k=3$：先翻转区间 $[1,3]$，得到 11000；再翻转区间 $[3,5]$，得到 11111。不存在更大的可行 $k$。

数据范围

• 对于所有数据，满足 $1\le t\le10000$。
• 对于所有数据，满足 $1\le n\le5000$。
• 对于所有数据，满足 $s_i\in\{0,1\}$。
• 所有测试组共同满足 $\sum n^2\le25000000$。