← 返回题目列表

Codeforces · 1750/B

B. 最大子串

中文机器翻译题面 查看原题

二进制字符串是仅由字符 0 和 1 组成的字符串。您将获得一个二进制字符串 $$$s$$$。

对于字符串$$$s$$$中包含$$$x$$$字符0和$$$y$$$字符1的非空子串$$$^\dagger$$$ $$$t$$$,定义其成本为:

- $$$x \cdot y$$$,如果 $$$x > 0$$$ 且 $$$y > 0$$$;
- $$$x^2$$$,如果 $$$x > 0$$$ 且 $$$y = 0$$$;
- $$$y^2$$$,如果 $$$x = 0$$$ 且 $$$y > 0$$$。

给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,找到其所有非空子串的最大成本。

$$$^\dagger$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过删除开头的几个(可能是零个或全部)字符和结尾的几个(可能是零个或全部)字符从 $$$b$$$ 获得。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。

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

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

输出

对于每个测试用例,打印一个整数 - 所有子字符串的最大成本。

示例

输入 #1

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

输出 #1

9
12
16
12
9
1

注意

在第一个测试用例中,我们可以采用子字符串$$$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$$$。