CF2106F Goblin

TC 博士有一位新病人叫哥布林。他想测试哥布林的智力，但对标准测试感到厌倦了，于是决定增加难度。 首先，他创建一个长度为 $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}$。 一个大小为 $k$ 的集合 $S$ 被认为是好的，如果它满足以下条件： 1. 对于所有 $1 \leq i \leq k$，有 $1 \leq x_i, y_i \leq n$； 2. 对于所有 $1 \leq i \leq k$，有 $g_{x_i, y_i} = \texttt{0}$； 3. 对于任意两个整数 $i$ 和 $j$（$1 \leq i, j \leq k$），坐标 $(x_i, y_i)$ 可以通过一系列相邻的（共享一条边的）值为 $\texttt{0}$ 的单元格到达 $(x_j, y_j)$。 哥布林的任务是找出一个好的集合 $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$。

对于每个测试用例，输出一个数字，表示网格中好的单元格集合的最大可能大小。

在第一个示例中，网格如下： ``` 1 0 0 0 1 0 0 0 1 ``` 由单元格 $(1, 2)$ 和 $(1, 3)$ 组成的集合是好的。由单元格 $(1, 1)$ 和 $(1, 2)$ 组成的集合不是好的，因为单元格 $(1, 1)$ 的值不是 $\texttt{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$。 翻译由 DeepSeek V3 完成