题目描述

在一组数据中，相邻两个数的乘积代表着这个数对的美丽值。给出 $n$ 个数，你可以移除其中任意个数（但移除后剩余元素不能少于 $2$ 个），使得剩余数据的最大美丽值尽可能大。求能够达到的最大美丽值。

输入格式

本题包含多组输入。

第一行：一个整数 $T$，表示数据组数。

对于每组数据，需输入两行：

第一行：一个整数 $n$，表示数据个数；

第二行：$n$ 个整数 $a_1,a_2,...,a_n$，分别表示每个元素。

输出格式

一个整数，表示美丽值最大值。

样例

7
4
5 0 2 1
3
-1 1 0
5
2 0 -1 -4 0
6
-8 4 3 7 1 -9
6
0 3 -2 5 -4 -4
2
1000000000 910000000
7
-1 -7 -2 -5 -4 -6 -3

10
0
4
72
16
910000000000000000
42

样例 $1$ 解释

对于第一组数据，移除 $0$ 即可。

数据范围

对于 $100\%$ 的数据，$1≤T≤10^4，2≤n≤2×10^5，-10^9≤a_i≤10^9$。同一测试点中，各组数据的 $n$ 总和不超过 $2×10^5$。