B. JoJo's Incredible Adventurestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputDid 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".InputEach 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.OutputFor 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.ExampleInput
501101011110101010Output
0
1
2
6
1
NoteIn 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: 101110011 In the fourth test case, there is a table: 011110001111100111110011111001111100 In the fifth test case, there is a table: 101010010101101010010101101010010101 Rectangles with maximum area are shown in bold.
501101011110101010
0 1 2 6 1 
['math', 'strings', 'two pointers', '*1100']