给出长度为 $$$n$$$ 的二进制字符串 $$$s$$$。二进制字符串是仅由字符“1”和“0”组成的字符串。
您可以选择一个整数 $$$k$$$ ($$$1 \le k \le n$$$),然后多次应用以下操作:选择字符串中的 $$$k$$$ 连续字符并将它们反转,即将所有 '0' 替换为 '1',反之亦然。
使用这些操作,您需要使字符串中的所有字符等于“1”。
例如,如果 $$$n=5$$$、$$$s=00100$$$,则可以选择 $$$k=3$$$ 并按以下步骤操作:
- 选择从$$$1$$$-st到$$$3$$$-rd字符的子串,得到$$$s=\color{blue}{110}00$$$;
- 选择从$$$3$$$-rd到第$$$5$$$个字符的子串,得到$$$s=11\color{blue}{111}$$$;
使用所描述的操作找到可以使字符串中的所有字符等于“1”的 $$$k$$$ 的最大值。请注意,实现此目的所需的操作数量并不重要。
输入
第一行包含一个整数 $$$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”的字符串 $$$s$$$。
示例
输入 #1
5 5 00100 5 01000 7 1011101 3 000 2 10
输出 #1
3 2 4 3 1