题目描述

给定一个长度为 $n$ 的二进制字符串 $s$，构建一个 $n \times n$ 的方格表。首行写下原始字符串 $s$，次行右移一个字符的循环移位字符串 $s$，第三行右移两个字符的循环移位字符串 $s$，以此类推。因此，第 $k$ 行包含一个从 $s$ 右移 $k$ 个字符的循环移位字符串。行从上到下编号 $0$ 至 $n-1$。

在生成的表中，需要找到只由数字 $1$ 构成的矩形并计算其面积，返回最大的面积。

注意：字符串 $s$ 向右循环移动 $k$ 位是指将其最后 $k$ 个字符移动到前面，即字符串 $s_{n-k+1} \cdots s_n \; s_1 \cdots s_{n-k}$。

输入格式

第一行的正整数 $t$ ($1\leq t\leq 2\times10^4$) 是测试用例的数量。 对于每个测试用例，只有一行，是一个只由零和一组成的二进制字符串。

保证所有测试用例中字符总数之和不超过 $2\times 10^5$。

输出格式

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

样例

5
0
1
101
011110
101010

0
1
2
6
1