题目描述

一个二进制字符串是只包含字符 $0$ 和 $1$ 的字符串。给定一个二进制字符串 $s$。

对于 $s$ 的某个非空子串 $^\dagger$ $t$，其中包含 $x$ 个字符 $0$ 和 $y$ 个字符 $1$，其代价定义如下：

• 若 $x>0$ 且 $y>0$，则代价为 $x \cdot y$；
• 若 $x>0$ 且 $y=0$，则代价为 $x^2$；
• 若 $x=0$ 且 $y>0$，则代价为 $y^2$。

给定长度为 $n$ 的二进制字符串 $s$，请你求出所有非空子串中的最大代价。

$^\dagger$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可以通过删除 $b$ 最开头和最末尾的若干（可能为 $0$ 或全部）字符得到。

输入格式

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例个数。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个二进制字符串 $s$，其长度为 $n$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示所有子串中的最大代价。

说明/提示

在第一个测试用例中，可以选择子串 $111$。它包含 $3$ 个字符 $1$ 和 $0$ 个字符 $0$，所以 $a=3$，$b=0$，代价为 $3^2=9$。

在第二个测试用例中，可以选择整个字符串。它包含 $4$ 个字符 $1$ 和 $3$ 个字符 $0$，所以 $a=4$，$b=3$，代价为 $4 \cdot 3=12$。

在第三个测试用例中，可以选择子串 $1111$，其代价为 $4^2=16$。

在第四个测试用例中，可以选择整个字符串，代价为 $4 \cdot 3=12$。

在第五个测试用例中，可以选择子串 $000$，其代价为 $3 \cdot 3=9$。

在第六个测试用例中，只能选择子串 $0$，其代价为 $1 \cdot 1=1$。

由 ChatGPT 5 翻译

样例

6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0

9
12
16
12
9
1