TC 博士有一个新病人,名叫 Goblin。他想测试哥布林的智力,但他已经厌倦了标准测试。因此,他决定加大难度。
首先,他创建一个具有 $$$n$$$ 个字符的二进制字符串$$$^{\text{*}}$$$ $$$s$$$。然后,他创建 $$$n$$$ 二进制字符串 $$$a_1, a_2, \ldots, a_n$$$。已知 $$$a_i$$$ 是通过首先复制 $$$s$$$ 创建的,然后翻转第 $$$i$$$ 个字符($$$\texttt{1}$$$ 变为 $$$\texttt{0}$$$,反之亦然)。创建完所有 $$$n$$$ 字符串后,他将它们排列成 $$$n \times n$$$ 网格 $$$g$$$,其中 $$$g_{i, j} = a_{i_j}$$$。
包含不同整数对 $$$\{(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)\}$$$ 的大小为 $$$k$$$ 的集合 $$$S$$$ 被认为是好的,如果:
- $$$1 \leq x_i, y_i \leq n$$$ 对于所有 $$$1 \leq i \leq k$$$。
- $$$g_{x_i, y_i} = \texttt{0}$$$ 对于所有 $$$1 \leq i \leq k$$$。
- 对于任意两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq k$$$),坐标 $$$(x_i, y_i)$$$ 可以从坐标 $$$(x_j, y_j)$$$ 到达,方法是遍历一系列相邻单元格(共享一条边),这些单元格的值为$$$\texttt{0}$$$。
Goblin 的任务是找到一个好集合 $$$S$$$ 的最大可能大小。因为TC博士很慷慨,这次他给了他两秒钟来找到答案,而不是一秒钟。哥布林并不以诚实着称,所以他请你帮助他作弊。
$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$\texttt{1}$$$ 和 $$$\texttt{0}$$$ 组成的字符串。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^3)$$$ — 测试用例的数量。
每个测试的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — 二进制字符串 $$$s$$$ 的长度。
每个测试的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个数字,即网格中一组良好单元格的最大可能大小。
示例
输入复制
6300040010710110014000121110
输出复制
3 9 10 7 1 0
注意
在第一个示例中,黑板上写了以下网格:
$$$$$$ 1 0 0 $$$$$$ $$$$$$ 0 1 0 $$$$$$ $$$$$$ 0 0 1 $$$$$$
由单元格 $$$(1, 2)$$$ 和 $$$(1, 3)$$$ 组成的集合很好。由单元格 $$$(1, 1)$$$ 和 $$$(1, 2)$$$ 组成的集合不好,因为单元格 $$$(1, 1)$$$ 的值不是 $$$0$$$。单元格集 $$$(1, 2)$$$、$$$(1, 3)$$$、$$$(2, 3)$$$ 很好,最大尺寸为 $$$3$$$。请注意,单元格集 $$$(2, 1)$$$、$$$(3, 1)$$$ 和 $$$(3, 2)$$$ 也很好,最大大小为 $$$3$$$。
在第二个示例中,黑板上写有以下网格:
$$$$$$ 1 0 1 0 $$$$$$ $$$$$$ 0 1 1 0 $$$$$$ $$$$$$ 0 0 0 0 $$$$$$ $$$$$$ 0 0 1 1 $$$$$$
一个好集合的最大可能大小是 $$$9$$$。