H. Maximum Product
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, you need to find $$${\displaystyle\max_{1 \le i \lt j \lt k \le n}{a_i\cdot a_j \cdot a_k}}$$$

Input

The first line contains an integer $$$t$$$ $$$(1\le t\le 10^5)$$$ — the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(3\le n \le 10^5)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(|a_i| \le 10^6)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test, print the answer in a single line.

Example
Input
2
4
-2 0 1 2
3
5 1 -3
Output
0
-15