CF1955E Long Inversions

给定一个长度为 $n$ 的 $01$ 字符串 $s$。$01$ 字符串是指只包含字符 `1` 和 `0` 的字符串 可以选定一个整数 $k\;(1 \le k \le n )$，将字符串中的连续 $k$ 个字符进行替换，将 $0$ 替换成 $1$，$1$ 替换成 $0$。 当 $ n=5,s=00100 $时 , 你可以指定 $k=3$ ，做如下操作： - 翻转 $[1,3]$ 的子串：$ s={\color{blue}{110}}00 $ ; - 反转 $[3,5]$ 的子串：$ s=11\color{blue}{111} $ ; 经过不限次操作后，寻找能将 $01$ 字符串中的所有字符转换成 $1$ 的最大 $k$ 值。

第一行一个整数 $t\;(1 \le t \le 10^4)$，表示测试组数。 每组测试数据第一行一个整数 $n\;(1 \le n \le 5000)$，字符串 $s$ 的长度。 第二行一个长度为 $n$ 的字符串 $s$，只包含 `1` 和 `0`。 保证所有测试数据中 $n^2$ 的总和不超过 $25 \times 10^6$。

每组测试数据输出一个整数 $k\;(1 \le k \le n)$，表示能通过操作把字符串变成全 `1` 的最大 $k$ 值。