You are given an array of integers $a_1,a_2,\ldots,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\le t\le 2 \cdot 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\le n\le 10^5$) — the size of the array.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-3\times 10^3\le a_i\le 3\times 10^3$) — given array.

It's guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 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)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120$.

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

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

In the fourth test case, choosing $a_1,a_2,a_3,a_4,a_6$ is a best choice: $(-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945$.

Difficulty: interview

Starter code:

Solutions:
def read_line():
    return list(map(int, input().split()))
def pr(l):
    a = 1
    for x in l:
        a *= x
    return a

T = int(input())
for _ in range(T):
    n = int(input())
    l = list(sorted(read_line()))
    l2 = list(reversed(l))
    m = None
    for i in range(6):
        j = 5 - i
        a = l[:i]
        b = l2[:j]
        p = pr(a) * pr(b)
        if m == None or p > m:
            m = p
    print(m)




t = int(input())

for _ in range(t):
    n = int(input())
    k = sorted(map(int, input().strip().split()))
    a, b = k[0] * k[1], k[2] * k[3]
    c, d = k[-5] * k[-4], k[-3] * k[-2]
    e = k[-1]

    print(max(a*b*e, a*d*e, c*d*e))

import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(lst):  # fix inputs here
    console("----- solving ------")

    maxres = lst[0] * lst[1] * lst[2] * lst[3] * lst[4]

    if 0 in lst:
        maxres = max(maxres, 0)

    positives = sorted([a for a in lst if a >= 0])[::-1]
    negatives = sorted([a for a in lst if a < 0])

    if len(positives) >= 5 and len(negatives) >= 0:
        maxres = max(maxres, positives[0]* positives[1]* positives[2]* positives[3]* positives[4])

    if len(positives) >= 3 and len(negatives) >= 2:
        maxres = max(maxres, positives[0]* positives[1]* positives[2]* negatives[0]* negatives[1])

    if len(positives) >= 1 and len(negatives) >= 4:
        maxres = max(maxres, positives[0]* negatives[0]* negatives[1]* negatives[2]* negatives[3])

    if len(negatives) >= 5:
        maxres = max(maxres, negatives[-1]* negatives[-2]* negatives[-3]* negatives[-4]* negatives[-5])

    # return a string (i.e. not a list or matrix)
    return maxres


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

for case_num in range(int(input())):
    # read line as a string
    # strr = input()

    # read line as an integer
    k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(lst)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)


from functools import reduce

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ng, ps = [], []
    for i in a:
        if i < 0:
            ng.append(-i)
        else:
            ps.append(i)
    ps.sort(reverse=True)
    ng.sort(reverse=True)
    ans = max(
            reduce(int.__mul__, ps[:5]) if len(ps) >= 5 else -10 ** 30,
            reduce(int.__mul__, ps[:3] + ng[:2]) if len(ps) >= 3 and len(ng) >= 2 else -10 ** 30,
            reduce(int.__mul__, ps[:1] + ng[:4]) if len(ps) >= 1 and len(ng) >= 4 else -10 ** 30
    )
    if 0 in a:
        ans = max(ans, 0)
    ps.sort()
    ng.sort()
    ans = max(
            ans,
            -reduce(int.__mul__, ps[:4] + ng[:1]) if len(ps) >= 4 and len(ng) >= 1 else -10 ** 30,
            -reduce(int.__mul__, ps[:2] + ng[:3]) if len(ps) >= 2 and len(ng) >= 3 else -10 ** 30,
            -reduce(int.__mul__, ng[:5]) if len(ng) >= 5 else -10 ** 30
    )
    print(ans)

t = int(input())
for _ in range(t):
    solve()

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    x=a[-1]*a[-2]*a[-3]*a[-4]*a[-5]
    y=a[0]*a[1]*a[-1]*a[-2]*a[-3]
    z=a[0]*a[1]*a[2]*a[3]*a[-1]
    print(max(x, y, z))

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

def giveanswer(l):
    
    ans = -float('inf')
    for i in range(6):
        ans = max(ans ,l[i - 1] * l[i - 2] * l[i - 3] * l[i - 4] * l[i - 5])
    return ans

for _ in range(val()):
    n = val()
    print(giveanswer(sorted(li())))


for _ in range(int(input())):
    n = int(input())
    neg = []
    pos = []
    zero = False
    for e in map(int, input().split()):
        if e < 0:
            neg.append(e)
        elif e > 0:
            pos.append(e)
        else:
            zero = True
    neg.sort()
    pos.sort()
    res = -float("inf")
    if zero:
        res = 0
    for i in range(6): # i = number of -
        if len(neg) < i or len(pos) < 5-i:
            continue
        ar = neg[-i:] + pos[:5-i]
        if i % 2 == 0:
            ar = neg[:i] + pos[-(5-i):]
        #print(i, ar)
        acc = 1
        for e in ar:
            acc *= e
        res = max(res, acc)
    print(res)


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    ans=0
    t1=a[0]*a[1]*a[2]*a[3]*a[-1]
    t2=a[0]*a[1]*a[-2]*a[-3]*a[-1]
    t3=a[-5]*a[-4]*a[-2]*a[-3]*a[-1]
    
    print(max(t1,t2,t3))

import sys

T = int(sys.stdin.readline().strip())
for t in range (0, T):
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    a.sort()
    print(max([a[0] * a[1] * a[2] * a[3] * a[-1], 
        a[0] * a[1] * a[-3] * a[-2] * a[-1], 
        a[-5] * a[-4] * a[-3] * a[-2] * a[-1]]))

import sys
input = sys.stdin.readline
from math import gcd
from operator import mul
from functools import reduce
 
t = int(input())

for _ in range(t):
    n = int(input())
    arr = list(map(int,input().split()))
 
    arr.sort()
    best = - (10**99)
    
    tmp = arr[-5:]
    tmp = reduce(lambda x, y: x * y, tmp, 1)
    best = max(best, tmp)
    
    tmp = arr[:2] + arr[-3:]
    tmp = reduce(lambda x, y: x * y, tmp, 1)
    best = max(best, tmp)
    
    tmp = arr[:4] + arr[-1:]
    tmp = reduce(lambda x, y: x * y, tmp, 1)
    best = max(best, tmp)
    
    print(best)

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    pos,neg = 0,0
    for i in arr:
        if i>0:
            pos+=1
        elif i<0:
            neg+=1
    ans = -10**18
    arr.sort()
    i = 0
    while i<=4 and i<=neg:
        cur = 1
        for j in range(i):
            cur = cur*arr[j]
        j = n-1
        while j>=(n-(5-i)):
            cur = cur*arr[j]
            j-=1
        ans = max(ans,cur)
        i+=2
    print(ans)

# Anuneet Anand

T = int(input())

while T:
	n = int(input())
	A = list(map(int,input().split()))
	A.sort()

	a = A[n-1]*A[n-2]*A[n-3]*A[n-4]*A[n-5]
	b = A[n-1]*A[n-2]*A[n-3]*A[0]*A[1]
	c = A[n-1]*A[0]*A[1]*A[2]*A[3]

	print(max(a,b,c))

	T = T - 1






t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    m = []
    p = []
    cnt0 = 0
    for val in a:
        if val > 0:
            p.append(val)
        elif val < 0:
            m.append(val)
        else:
            cnt0 += 1
    p = sorted(p, reverse=True)
    m = sorted(m)
    
    # ppppp
    ans = -10 ** 20
    tmp = 1
    if len(p) >= 5:
        for i in range(5):
            tmp *= p[i]
        ans = max(tmp, ans)
    # ppppm
    tmp = 1
    if len(p) >= 4 and len(m) >= 1:
        for i in range(4):
            tmp *= p[~i]
        for i in range(1):
            tmp *= m[~i]
        ans = max(tmp, ans)
    # pppmm
    tmp = 1
    if len(p) >= 3 and len(m) >= 2:
        for i in range(3):
            tmp *= p[i]
        for i in range(2):
            tmp *= m[i]
        ans = max(tmp, ans)
    # ppmmm
    tmp = 1
    if len(p) >= 2 and len(m) >= 3:
        for i in range(2):
            tmp *= p[~i]
        for i in range(3):
            tmp *= m[~i]
        ans = max(tmp, ans)
    # pmmmm
    tmp = 1
    if len(p) >= 1 and len(m) >= 4:
        for i in range(1):
            tmp *= p[i]
        for i in range(4):
            tmp *= m[i]
        ans = max(tmp, ans)
    # mmmmm
    tmp = 1
    if len(m) >= 5:
        for i in range(5):
            tmp *= m[~i]
        ans = max(tmp, ans)
    if cnt0 > 0:
        ans = max(0, ans)

    print(ans)