CF1820B.JoJo's Incredible Adventures

Did you think there was going to be a JoJo legend here? But no, that was me, Dio!

Given a binary string $s$ of length $n$, consisting of characters 0 and 1. Let's build a square table of size $n \times n$, consisting of 0 and 1 characters as follows.

In the first row of the table write the original string $s$. In the second row of the table write cyclic shift of the string $s$ by one to the right. In the third row of the table, write the cyclic shift of line $s$ by two to the right. And so on. Thus, the row with number $k$ will contain a cyclic shift of string $s$ by $k$ to the right. The rows are numbered from $0$ to $n - 1$ top-to-bottom.

In the resulting table we need to find the rectangle consisting only of ones that has the largest area.

We call a rectangle the set of all cells $(i, j)$ in the table, such that $x_1 \le i \le x_2$ and $y_1 \le j \le y_2$ for some integers $0 \le x_1 \le x_2 \lt n$ and $0 \le y_1 \le y_2 \lt n$.

Recall that the cyclic shift of string $s$ by $k$ to the right is the string $s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$. For example, the cyclic shift of the string "01011" by $0$ to the right is the string itself "01011", its cyclic shift by $3$ to the right is the string "01101".

你以为这里会有一个乔乔的传说吗？但其实是我，迪奥！

给定一个长度为 $n$ 的二进制字符串 $s$，由字符 0 和 1 组成。我们按如下方式构造一个大小为 $n \times n$ 的、仅含 0 和 1 的方阵。

• 在表格的第一行（即第 $0$ 行）写入原始字符串 $s$；
• 在第二行（即第 $1$ 行）写入字符串 $s$ 向右循环移动一位后的结果；
• 在第三行（即第 $2$ 行）写入字符串 $s$ 向右循环移动两位后的结果；
• 依此类推……
  因此，第 $k$ 行（行号从 $0$ 到 $n-1$，自上而下编号）包含字符串 $s$ 向右循环移动 $k$ 位后的结果。

在该方阵中，我们需要找出全由 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"。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of test cases follows.

The first and the only line of each test case contains a single binary string $s$ ($1 \le \lvert s \rvert \le 2 \cdot 10^5$), consisting of characters 0 and 1.

It is guaranteed that the sum of string lengths $|s|$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the maximum area of a rectangle consisting only of ones. If there is no such rectangle, output $0$.

对于每个测试用例，输出一个整数——仅由数字 1 构成的矩形的最大面积。如果不存在这样的矩形，则输出 $0$。

In the first test case, there is a table $1 \times 1$ consisting of a single character 0, so there are no rectangles consisting of ones, and the answer is $0$.

In the second test case, there is a table $1 \times 1$, consisting of a single character 1, so the answer is $1$.

In the third test case, there is a table:

1

0

1

1

1

0

0

1

1

In the fourth test case, there is a table:

0

1

1

1

1

0

0

0

1

1

1

1

1

0

0

1

1

1

1

1

0

0

1

1

1

1

1

0

0

1

1

1

1

1

0

0

In the fifth test case, there is a table:

1

0

1

0

1

0

0

1

0

1

0

1

1

0

1

0

1

0

0

1

0

1

0

1

1

0

1

0

1

0

0

1

0

1

0

1

Rectangles with maximum area are shown in bold.

在第一个测试用例中，存在一个 $1 \times 1$ 的表格，仅包含单个字符 0，因此不存在全由 1 组成的矩形，答案为 $0$。

在第二个测试用例中，存在一个 $1 \times 1$ 的表格，仅包含单个字符 1，因此答案为 $1$。

在第三个测试用例中，存在如下表格：

1

0

1

1

1

0

0

1

1

在第四个测试用例中，存在如下表格：

0

1

1

1

1

0

0

0

1

1

1

1

1

0

0

1

1

1

1

1

0

0

1

1

1

1

1

0

0

1

1

1

1

1

0

0

在第五个测试用例中，存在如下表格：

1

0

1

0

1

0

0

1

0

1

0

1

1

0

1

0

1

0

0

1

0

1

0

1

1

0

1

0

1

0

0

1

0

1

0

1

面积最大的矩形以粗体标出。