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.
#    ____                       _   _                _     _ _   
#   / ___| __ _ _ __ __ _      | | | | __ _ _ __ ___| |__ (_) |_ 
#  | |  _ / _` | '__/ _` |_____| |_| |/ _` | '__/ __| '_ \| | __|
#  | |_| | (_| | | | (_| |_____|  _  | (_| | |  \__ \ | | | | |_ 
#   \____|\__,_|_|  \__, |     |_| |_|\__,_|_|  |___/_| |_|_|\__|
#                   |___/                                        

from typing import Counter
import sys
from collections import defaultdict as dd
from math import *

def vinp():
    return map(int,input().split())
def linp():
    return list(map(int,input().split()))
def sinp():
    return input()
def inp():
    return int(input())
def mod(f):
    return f % 1000000007
def pr(*x):
    print(*x)
def finp():
    f=open("input.txt","r")
    f=f.read().split("\n")
    return f
def finp():
    f=open("input.txt","r")
    f=f.read().split("\n")
    return f
def fout():
    return open("output.txt","w")
def fpr(f,x):
    f.write(x+"\n")
def csort(c):
    sorted(c.items(), key=lambda pair: pair[1], reverse=True)
def indc(l,n):
    c={}
    for i in range(n):
        c[l[i]]=c.get(l[i],[])+[i+1]
    return c

if __name__ =="__main__":
    cou=inp()
    for i in range(cou):
        n=inp()
        l=linp()
        ans=0
        for i in range(n-1):
            a=min(l[i],l[i + 1])
            b=max(l[i],l[i + 1])
            ans = max(ans,a*b)
        pr(ans)