You are given an array of integers a_1,a_2,…,a_n. Find the maximum possible value of a_ia_ja_ka_la_t among all five indices (i, j, k, l, t) (i<j<k<l<t).

Input

The input consists of multiple test cases. The first line contains an integer t (1≤ t≤ 2 ⋅ 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (5≤ n≤ 10^5) — the size of the array.

The second line of each test case contains n integers a_1,a_2,…,a_n (-3× 10^3≤ a_i≤ 3× 10^3) — given array.

It's guaranteed that the sum of n over all test cases does not exceed 2⋅ 10^5.

Output

For each test case, print one integer — the answer to the problem.

Example

Input


4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1


Output


-120
12
0
945

Note

In the first test case, choosing a_1,a_2,a_3,a_4,a_5 is a best choice: (-1)⋅ (-2) ⋅ (-3)⋅ (-4)⋅ (-5)=-120.

In the second test case, choosing a_1,a_2,a_3,a_5,a_6 is a best choice: (-1)⋅ (-2) ⋅ (-3)⋅ 2⋅ (-1)=12.

In the third test case, choosing a_1,a_2,a_3,a_4,a_5 is a best choice: (-1)⋅ 0⋅ 0⋅ 0⋅ (-1)=0.

In the fourth test case, choosing a_1,a_2,a_3,a_4,a_6 is a best choice: (-9)⋅ (-7) ⋅ (-5)⋅ (-3)⋅ 1=945.
'''# Author : -pratyay-
import sys
inp=sys.stdin.buffer.readline
inar=lambda: list(map(int,inp().split()))
inin=lambda: int(inp())
inst=lambda: inp().decode().strip()
wrt=sys.stdout.write
pr=lambda *args,end='\n': wrt(' '.join([str(x) for x in args])+end)
enum=enumerate
inf=float('inf')
# Am I debugging ? Check if I'm using same variable name in two places
# fun() returning empty list ? check new=temp[:] or new=temp

_T_=inin()
for _t_ in range(_T_):
    n=inin()
    a=inar()
    last=[-1 for i in range(n+1)]
    gap=[-1 for i in range(n+1)]
    for i in range(n):
        gap[a[i]]=max(gap[a[i]],i-last[a[i]])
        last[a[i]]=i
    for i in a:
        gap[i]=max(gap[i],n-last[i])
    gapmin=[inf for i in range(n+1)]
    for i in range(1,n+1):
        if gap[i]==-1:
            continue
        gapmin[gap[i]]=min(gapmin[gap[i]],i)
    for i in range(1,n+1):
        gapmin[i]=min(gapmin[i-1],gapmin[i])
    for i in range(n+1):
        if gapmin[i]==inf:
            gapmin[i]=-1
    pr(*gapmin[1:])


# react.js
# javascript
# node.js
# async await, fetch

# dunzo
# cred
# freecharge
# share chat -> they ask, how operating system works
# threading
# Air bnb'''
'''
import pyttsx3
import datetime
import speech_recognition as sr

engine = pyttsx3.init('sapi5')
voices = engine.getProperty('voices')
#print(voices)
engine.setProperty('voice',voices[0].id)
def userInit():
    print("Login Name : ",end='')
    _name_=input()
    return _name_ 

def speak(audio):
    engine.say(audio)
    engine.runAndWait()

def wishMe(User):
    hour = int(datetime.datetime.now().hour)
    if hour>=0 and hour<12:
        speak("Good Morning")

    elif hour>=12 and hour<18:
        speak("Good Evening")


    speak("Jarvis here {}, whatcha wanna do?".format(User))       

def takeCommand():
    #It takes mocrophone input from user and returns string output

    r = sr.Recognizer()
    with sr.Microphone() as source:
        print("Listening...")
        r.pause_threshold = 1
        audio = r.listen(source)



if __name__ == "__main__":
    User=userInit()
    wishMe(User)
    a=input()
    sad=['Sad','sad','SAD']
    sadbool=False
    for i in sad:
        if i in a:
            sadbool=True 
    if sadbool:
        speak("Why are you sad? man")

'''

# Author : Pratyaydeep↯Ghanta
import sys,threading
# Am I debugging, check if I'm using same variable name in two places
from functools import reduce
def mul(a):
    if a==[]:
        return 1
    return reduce(lambda x,y:x*y, a)
def main():
    _T_,=read()
    for _t_ in range(_T_):
        n,=read()
        ar=read()
        pos=[]
        neg=[]
        for i in ar:
            if i<0:
                neg.append(i)
            else:
                pos.append(i)
        neg.sort()
        pos.sort()
        #print(neg)
        #print(pos)
        #print(mul(neg))
        ans=-float('inf')
        for k in range(6):
            p=k
            ne=5-k
            if len(pos)>=p and len(neg)>=ne:
                if ne%2==0:
                   ans=max(ans,mul(pos[-p:])*mul(neg[:ne]))
                else:
                    ans=max(ans,mul(pos[-p:])*mul(neg[-ne:]))
                    #print(neg[:ne])
        print(ans)

# Template -> Pratyaydeep
def inpt(): return sys.stdin.readline().rstrip()
def read(): return [int(x) for x in inpt().split()]
if (0):
    sys.setrecursionlimit(10**7)
    threading.stack_size(10**8)
    threading.Thread(target=main).start()
else:
    main()