human
PYTHON3 solution for "You are given n integers a_1, a_2, …, a_n. Find the maximum value of max(a_l, a_{l + 1}, …, a_r) ⋅ min(a_l, a_{l + 1}, …, a_r) over all pairs (l, r) of integers for which 1 ≤ l < r ≤ n.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (2 ≤ n ≤ 10^5).

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^6).

It is guaranteed that the sum of n over all test cases doesn't exceed 3 ⋅ 10^5.

Output

For each test case, print a single integer — the maximum possible value of the product from the statement.

Example

Input

4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

Output

12
6
4761
381274500335

Note

Let f(l, r) = max(a_l, a_{l + 1}, …, a_r) ⋅ min(a_l, a_{l + 1}, …, a_r).

In the first test case, 

  * f(1, 2) = max(a_1, a_2) ⋅ min(a_1, a_2) = max(2, 4) ⋅ min(2, 4) = 4 ⋅ 2 = 8. 
  * f(1, 3) = max(a_1, a_2, a_3) ⋅ min(a_1, a_2, a_3) = max(2, 4, 3) ⋅ min(2, 4, 3) = 4 ⋅ 2 = 8. 
  * f(2, 3) = max(a_2, a_3) ⋅ min(a_2, a_3) = max(4, 3) ⋅ min(4, 3) = 4 ⋅ 3 = 12. 


So the maximum is f(2, 3) = 12.

In the second test case, the maximum is f(1, 2) = f(1, 3) = f(2, 3) = 6.":



=====
Give me a Python program to find the maximum value of max(a_l, a_{l + 1}, …, a_r) ⋅ min(a_l, a_{l + 1}, …, a_r) over all pairs (l, r) of integers for which 1 ≤ l < r ≤ n?
assistant
#Here is Python program to find the maximum value of max(a_l, a_{l + 1}, …, a_r) ⋅ min(a_l, a_{l + 1}, …, a_r) over all pairs (l, r) of integers for which 1 ≤ l < r ≤ n.
 # python
import os
import sys; import math
from io import BytesIO, IOBase
from operator import itemgetter

def solve():
    n = int(input()); a = [int(x) for x in input().split()]; Max = []
    for i in range(n-1):
        Max.append(a[i]*a[i+1])
    print(max(Max))

def upperbound(arr,val):
    start = 0; end = len(arr) - 1; ans = -1
    while (start <= end):
        mid = (start + end) // 2
        if (arr[mid] <= val):
            start = mid + 1
        else:
            ans = mid
            end = mid - 1
    return ans
def lowerbound(arr,val):
    length = len(arr); answer = -1; start = 0; end = length - 1    
    while start <= end:
        middle = (start + end)//2    
        if arr[middle] == val:
            answer = middle
            end = middle - 1
        elif arr[middle] > val:
            end = middle - 1    
        else:
            start = middle + 1
    return answer
def D2B(n):
    arr = []
    while (n > 0):
        temp = n; m = 0; p = 1
        while (temp):
            rem = temp % 10; temp = int(temp/10)
            if (rem != 0):
                m += p;
            p *= 10;
        arr.append(m); n = n - m;
    return arr
def sort2D(arr,axis):
    arr = sorted(arr, key = itemgetter(axis)); return arr
def DD(rows,cols):
    arr = [[0 for i in range(cols)] for j in range(rows)]; return arr
# region fastio

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
        ...