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.
#######################################################################################################
#######        ###########         #######    #########    #######           ######               #####
######  ######  #########  ######  #######  ###########  #############   ################  ############
######  #######  ########  #######  ######  ###########  ##############  ################  ############
######  ######  #########  #######  ######               #############   ################  ############
######  ###   ###########  #######  ######  ###########  #############   ################  ############
######  #####  ##########  #######  ######  ###########  #############   ################  ############
######  ######  ##########  #####  #######  ###########  #############   ################  ############
####     ######     ######        ######    ########      #######            ##########     ###########
#######################################################################################################
import sys
#-----------------------IMPORTANT  FUNCTIONS ---------------------------------#
from math import cos, pi, ceil, pi, tan, floor, gcd, sqrt, log2, factorial, log10
from collections import Counter
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase
from statistics import mean, median, mode

alpha = ascii_lowercase
beta = ascii_uppercase


#-----------------------NEXT POWER OF 2---------------------------------------#
def nextPowerOf2(n):
    p = 1
    if (n and not (n & (n - 1))):
        return n
    while (p < n):
        p <<= 1
    return p


#-----------------------GET DIVISORS 1 TO <=N   ------------------------------#
def get_Divisors(n):
    arr = []
    i = 1
    while i <= sqrt(n):
        if (n % i == 0):
            if (n / i == i):
                arr.append(i)
            else:
                arr.append(i)
                arr.append(n // i)
        i = i + 1

    return arr


#----------------------CHECK    PRIMES-----------------------------------#
def isprime(n):
    if n == 1:
        return 0
    i = 2
    while (i * i <= n):
        if (n % i == 0):
            return 0
        i += 1
    return 1


#-----------------------PRE COMPUTED  PRIMES-----------------------------------#
def Sieve(n):
    prime = [True for i in range(n + 1)]
    prime[0] = False
    prime[1] = False
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    return prime


#-----------------------LARGER VALUE OF  X,Y,10**9+7 --------------------------#
def power(x, y, p):
    res = 1
    x = x % p
    if (x == 0):
        return 0
    while (y > 0):
        if ((y & 1) == 1):
            res = (res * x) % p
        y = y >> 1
        x = (x * x) % p
    return res


#-----------------------       CREATE MATRIX         --------------------------#
def create_matrix(n, m):
    mat = [[] for i in range(n)]
    for i in range(n):
        for j in range(m):
            mat[i].append(0)
    return mat


#By Default Counter stores the value in decending orderCounter({4: 2, 8: 2, 2: 1, 9: 1}
#s=sorted(s.items(),key=lambda k:(k[0],k[1])) ---> [(2, 1), (4, 2), (8, 2), (9, 1)]
#sort 2nd value  from bada se chhota  then(4,2)(8,2)->>(8,2)(4,2) s=sorted(s.items(),key=lambda k:(-k[1],-k[0]))  [(8, 2), (4, 2), (9, 1), (2, 1)]
#for list pair in a list    s.sort(key=lambda k:(-k[1],-k[0])) [[3, 4], [8, 2], [4, 2]]
# from functools import cmp_to_key
# def compare(x, y):
#     if x + y > y + x:
#         return -1
#     elif x + y < y + x:
#         return 1
#     else:
#         return 0
#how to use compare ----ss = sorted(s, key=cmp_to_key(compare))
#-----------------------*****CODE STARTS  HERE*****--------------------------#
# sys.stdout = open('ot.txt', 'w')
# sys.stdin = open('in.txt', 'r')
def main():
    for ttt in range(int(input())):
        n = int(input())
        arr=list(map(int,input().split()))
        mx=max(arr)
        maxi=[]
        for i in range(n):
            if arr[i]==mx:
                maxi.append(i)
        an=0
        for mx in maxi: 
            ans=0
            if mx==n-1:
                ans=arr[n-1]*arr[n-2]
            elif mx==0:
                ans=arr[0]*arr[1]
            else:
                ans=max(arr[mx]*arr[mx-1],arr[mx]*arr[mx+1])
            an=max(an,ans)
        print(ans)
            
        
        
if __name__ == "__main__":
    main()
