二进制字符串是仅由字符 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$$$。