Karina has an array of n integers a1,a2,a3,…,an. She loves multiplying numbers, so she decided that the beauty of a pair of numbers is their product. And the beauty of an array is the maximum beauty of a pair of adjacent elements in the array.

For example, for n=4, a=[3,5,7,4], the beauty of the array is max

(3?5, 5?7, 7?4) = max(15, 35, 28) = 35.

Karina wants her array to be as beautiful as possible. In order to achieve her goal, she can remove some elements (possibly zero) from the array. After Karina removes all elements she wants to, the array must contain at least two elements.

Unfortunately, Karina doesn't have enough time to do all her tasks, so she asks you to calculate the maximum beauty of the array that she can get by removing any number of elements (possibly zero).

Input

The first line of the input contains an integer t (1≤t≤104) — the number of test cases.

The description of the test cases follows.

The first line of a test case contains an integer n (2≤n≤2?105) — the length of the array a.

The second line of a test case contains n integers a1,a2,a3,…,an(?109≤ai≤109) — the elements of the array a.

The sum of all values of n across all test cases does not exceed 2?105.

Output

Output t integers, each of which is the answer to the corresponding test case — the maximum beauty of the array that Karina can get.

-----------------------------------------------

Karina 有一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組 a1,a2,a3,…,an。 她喜歡數(shù)字相乘，因此她認(rèn)為一對(duì)數(shù)字的美妙之處在于它們的乘積。 而數(shù)組的美感就是數(shù)組中一對(duì)相鄰元素的最大美感。

例如，對(duì)于n=4，a=[3,5,7,4]，數(shù)組的美感為max

(3?5, 5?7, 7?4) = 最大值(15, 35, 28) = 35。

卡琳娜希望她的陣列盡可能漂亮。 為了實(shí)現(xiàn)她的目標(biāo)，她可以從數(shù)組中刪除一些元素（可能為零）。 卡琳娜 (Karina) 刪除她想要?jiǎng)h除的所有元素后，數(shù)組必須至少包含兩個(gè)元素。

不幸的是，卡琳娜沒有足夠的時(shí)間來完成她的所有任務(wù)，因此她要求您計(jì)算她通過刪除任意數(shù)量的元素（可能為零）可以獲得的數(shù)組的最大美感。

輸入

輸入的第一行包含一個(gè)整數(shù) t (1≤t≤104) — 測(cè)試用例的數(shù)量。

測(cè)試用例的描述如下。

測(cè)試用例的第一行包含一個(gè)整數(shù) n (2≤n≤2?105) — 數(shù)組 a 的長(zhǎng)度。

測(cè)試用例的第二行包含 n 個(gè)整數(shù) a1,a2,a3,…,an(?109≤ai≤109) — 數(shù)組 a 的元素。

所有測(cè)試用例中 n 的所有值的總和不超過 2?105。

輸出

輸出t個(gè)整數(shù)，每個(gè)整數(shù)都是對(duì)應(yīng)測(cè)試用例的答案——Karina可以獲得的數(shù)組的最大美感。

---------------------

就是計(jì)算乘積的最大值，因?yàn)樨?fù)負(fù)得正，所以有可能是負(fù)數(shù)，所以這里面要比較2個(gè)值，最大的兩個(gè)的乘積跟最小的兩個(gè)的乘積的大小。

下面是代碼：