你以为这里会出现JoJo传奇吗?但不,那是我,迪奥!
给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,由字符 0 和 1 组成。让我们构建一个大小为 $$$n \times n$$$ 的方桌,由 0 和 1 个字符组成,如下所示。
在表的第一行写入原始字符串$$$s$$$。在表的第二行中,将字符串 $$$s$$$ 向右循环移位一位。在表的第三行中,将 $$$s$$$ 行的循环移位向右写入 2。等等。因此,编号为 $$$k$$$ 的行将包含字符串 $$$s$$$ 向右循环移位 $$$k$$$。行从上到下从 $$$0$$$ 到 $$$n - 1$$$ 编号。
在结果表中,我们需要找到仅由面积最大的矩形组成的矩形。
我们将表中所有单元格 $$$(i, j)$$$ 的集合称为矩形,对于某些整数 $$$x_1 \le i \le x_2$$$ 和 $$$y_1 \le j \le y_2$$$ $$$0 \le x_1 \le x_2 < n$$$ 和 $$$0 \le y_1 \le y_2 < n$$$。
回想一下,字符串 $$$s$$$ 向右循环移位 $$$k$$$ 是字符串 $$$s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$$$。例如,字符串“01011”向右循环移位$$$0$$$就是字符串本身“01011”,其向右循环移位$$$3$$$就是字符串“01101”。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含一个二进制字符串 $$$s$$$ ($$$1 \le \lvert s \rvert \le 2 \cdot 10^5$$$),由字符 0 和 1 组成。
保证所有测试用例的字符串长度 $$$|s|$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——仅由 1 组成的矩形的最大面积。如果不存在这样的矩形,则输出$$$0$$$。
示例
输入 #1
5 0 1 101 011110 101010
输出 #1
0 1 2 6 1
注意
在第一个测试用例中,有一个由单个字符 0 组成的表 $$$1 \times 1$$$,因此不存在由 1 组成的矩形,答案为 $$$0$$$。
在第二个测试用例中,有一个表$$$1 \times 1$$$,由单个字符1组成,所以答案是$$$1$$$。
在第三个测试用例中,有一个表:
101110011
在第四个测试用例中,有一个表:
011110001111100111110011111001111100
第五个测试用例中有一张表:
101010010101101010010101101010010101
面积最大的矩形以粗体显示。