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 < n $ and $ 0 \le y_1 \le y_2 < 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".

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 $ .

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 $ .

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: 101110011In the fourth test case, there is a table: 011110001111100111110011111001111100In the fifth test case, there is a table: 101010010101101010010101101010010101Rectangles with maximum area are shown in bold.