← 返回比赛
已结束 GESP欢乐赛 #5
← 上一题 下一题 →

A1440 | 最大价值

来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

二进制字符串是一个仅由字符 0 和字符 1 组成的字符串。

对于一个包含 $x$ 个字符 0 和 $y$ 个字符 1 的 $s$ 的非空子串，将其价值定义为：
* 如果 $x > 0$ 并且 $y > 0$，$value = x * y$。
* 如果 $x > 0$ 并且 $y = 0$，$value = x * x$。
* 如果 $x = 0$ 并且 $y > 0$，$value = y * y$。

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

输入格式

每个测试由多个测试用例组成。

第一行包含一个整数 $T$ ($1 \le T \le 100$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 1 \times 10^5$) — 表示字符串的长度.

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

输出格式

对于每个测试用例，打印一个整数——表示 $s$ 所有非空子串中的最大价值。

输入输出样例

输入 #1
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
输出 #1
9
12
16
12
9
1
C++ 编辑器
输入
输出