H. 可爱串串
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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

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

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

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

Input

输入包含多组测试数据。

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

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

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

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

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

Output

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

Example
Input
5
3
100
4
1011
6
111011
3
111
8
11111111
Output
0
1
4
2
16
Note

以最后一组样例为例，

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

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

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