Today is Chocolate day and Ashu wants to impress Rosalind by giving her a box of chocolates. But is in a hurry to attend his HIREDIVE classes for GATE exam. So he asks you to buy a box of chocolate which consists of N chocolates. The total impress index of a box of chocolate depends on only first and last chocolate in the box which is given by multiplication of impressing index of 1st and last chocolate. Since Ashu wants to impress Rosalind thus he wants that impressing index of the box to be maximum. But Ashu is only allowed to rotate the chocolates inside the box.

Eg. If the box of chocolate is {8,2,3,7,5,1} He rotates the box in following manner to achieve the maximum impressing index of the box -> {8,2,3,7,5,1} Impressing Index = 8
-> {2,3,7,5,1,8} Impressing Index = 16
-> {3,7,5,1,8,2} Impressing Index = 6
-> {7,5,1,8,2,3} Impressing Index = 21
-> {5,1,8,2,3,7} Impressing Index = 35
-> {1,8,2,3,7,5} Impressing Index = 5
Thus the maximum Impressing Index of the box is 35.

Since Ashu is getting late for this HIREDIVE classes so he asked you to tell him the highest impressing index of the chocolate box.

INPUT:

First line of the input consists a single integer t the number of test cases. The t test cases follow in next lines.
Each test case consists of two lines, a single integer in the first line denoting the number of chocolates n in a box. The second line of the test case is n space separated integers A[i] denoting impressing index of i-th chocolate.

OUTPUT:

For each test case print the maximum impressing index of the box in a new line.

CONSTRAINTS:

1<=T<=100
1<=N<=10^5
1<=A[i]<=10^3