题目描述

光头强有一个包含 $n$ 个整数 $a_1,a_2,a_3,…,a_n$ 的数组。

他喜欢乘法，所以他定义一对数的美丽值是它们的乘积。数组的美丽值是数组中相邻元素对的最大美丽值。

例如，当 $n=4，a=[3,5,7,4]$ 时，数组的美丽值是 $max(3×5, 5×7, 7×4) = max(15, 35, 28) = 35$。

光头强希望他的数组尽可能美丽。为了实现他的目标，他可以删除一些元素（可能为零）从数组中。在光头强删除了所有他想删除的元素之后，数组必须包含至少两个元素。

不幸的是，光头强没有足够的数学知识完成任务，所以他要求你计算通过删除任意数量的元素（可能为零）他可以获得的数组的最大美丽值。

输入格式

第一行包含一个整数 $t(1≤t≤10^4)$- 测试用例的数量。

接下来是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n(2≤n≤2⋅10^5)$ - 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,a_3,…,a_n(-10^9≤a_i≤10^9)$ - 数组 $a$ 的元素。

所有测试用例中 $n$ 值的总和不超过 $2⋅10^5$。

输出格式

输出 $t$ 个整数，每个整数都是相应测试用例的答案- 光头强可以得到的数组的最大美丽值。

测试样例

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

样例说明

在示例的第一个测试用例中，为了获得最大的美丽值，你需要移除第二个元素。

在示例的第二和第三个测试用例中，不需要移除任何元素就可以获得最大的美丽值。

在示例的第四个测试用例中，你需要保留第一个和最后一个元素。