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.
from __future__ import division, print_function

MOD = 998244353
mod = 10**9 + 7

# import resource
# resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])

def prepare_factorial():
    fact = [1]
    for i in range(1, 100005):
        fact.append((fact[-1] * i) % mod)
    ifact = [0] * 100005
    ifact[100004] = pow(fact[100004], mod - 2, mod)
    for i in range(100004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod

    return fact, ifact

# import threading
# threading.stack_size(1<<27)
import sys
# sys.setrecursionlimit(10000)

# from bisect import bisect_left, bisect_right, insort
from math import floor, ceil, sqrt, degrees, atan, pi, log, sin, radians
# from heapq import heappop, heapify, heappush
from collections import Counter, defaultdict, deque
from itertools import permutations


def modinv(n, p):
    return pow(n, p - 2, p)

def ncr(n, r, fact, ifact):    # for using this uncomment the lines calculating fact and ifact
    t = (fact[n] * (ifact[r] * ifact[n-r]) % mod) % mod
    return t

def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()

"""*****************************************************************************************"""

def GCD(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return (x * y)//(GCD(x, y))

def get_xor(n):
    return [n, 1, n+1, 0][n % 4]

def get_n(P):    # this function returns the maximum n for which Summation(n) <= Sum
    ans = (-1 + sqrt(1 + 8*P))//2
    return ans

""" ********************************************************************************************* """


def main():

    def solve(Arr, n, p):

        Arr.sort()
        pro = 1

        if Arr[n-1] == 0 and p&1:
            return 0

        if Arr[n-1] <= 0 and p&1:
            for i in range(n-1, n-p-1, -1):
                pro *= Arr[i]
            return pro
        i = 0
        j = n-1
        if p&1:
            pro *= Arr[j]
            j -= 1
            p -= 1

        p >>= 1

        for itr in range(p):
            left = Arr[i] * Arr[i+1]
            right = Arr[j] * Arr[j-1]

            if left > right:
                pro *= left
                i += 2
            else:
                pro *= right
                j -= 2
        return pro

    T = int(input())
    while T:
        n = int(input())
        Arr = get_array()
        ans = solve(Arr, n, 5)
        print(ans)
        T -= 1



""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)


class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda: self.buffer.read().decode('ascii')
            self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

if __name__ == '__main__':
    main()
    # threading.Thread(target=main).start()