H-可爱串串_2025年华为杯广东工业大学程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

塑料有一个长度为 $n$ 的 $01$ 串 $S$ 。

定义一个 $01$ 串的可爱值为这个 $01$ 串中 $1$ 的数量减去 $0$ 的数量；

塑料将要从中间选一个位置将这个 $01$ 串切成连续且非空的两半。

他想要知道切开后这两个串的可爱值的乘积最大可以是多少，但他非常懒，想要你帮他算一下，并承诺算对了会给你一发 AC 作为奖励。

输入包含多组测试数据。

第一行一个正整数 $T$ ( $1 \leq T \leq 50000$ )，表示数据组数；

接下来对于每组测试数据，输入两行：

数据的第一行输入一个正整数 $n$ ( $2 \leq n \leq 10^5$ )，表示字符串长度；

数据的第二行输入一个长度为 $n$ 的 $01$ 串 $S$ 。

保证对于每个测试点下所有测试数据的 $n$ 之和不超过 $5 \times 10^5$ 。

对于每组测试数据，输出一个整数 $x$ ，表示题目中式子的最大值。

示例1

复制

复制

以最后一组样例为例，

若选择 $pos=2$ ，则乘积为 $2 \times 6 = 12$ ；

若选择 $pos=4$ ，则乘积为 $4 \times 4 = 16$ 。

可以证明， $16$ 即为乘积的最大值。