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.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class TaskB {
    public static void main(String[] arg) {
        final FastScanner in = new FastScanner(System.in);
        final PrintWriter out = new PrintWriter(System.out);
        final int T = in.nextInt();
        StringBuilder result = new StringBuilder();
        for(int t=0;t<T;t++){
            final int n = in.nextInt();
            final int[]a = in.readIntArr(n);
            result.append(solution(n, a)).append('\n');
        }
        out.print(result);
        out.close();
        in.close();
    }

    private static long solution(final int n,
                                 final int[] a) {
        List<Integer> aPositive = new ArrayList<>();
        List<Integer> aNegative = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(a[i]>=0){
                aPositive.add(a[i]);
            }else{
                aNegative.add(a[i]);
            }
        }
        Collections.sort(aPositive);
        Collections.sort(aNegative);
        List<Integer> comb = new ArrayList<>();
        comb.addAll(getLast6(aPositive));
        comb.addAll(getFirst6(aPositive));
        comb.addAll(getLast6(aNegative));
        comb.addAll(getFirst6(aNegative));
        int [] varians =  new int[comb.size()];
        for(int i=0;i<varians.length;i++){
            varians[i]=comb.get(i);
        }
        final int m = varians.length;
        long max =Long.MIN_VALUE;
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m;j++){
                for(int k=j+1;k<m;k++){
                    for(int l=k+1;l<m;l++){
                        for(int t=l+1;t<m;t++){
                            max = Math.max(max,
                                    1L*varians[i]
                                    *varians[j]
                                    *varians[k]
                                    *varians[l]
                                    *varians[t]
                            );           
                        }
                    }
                }
            }
        }
        return max;
    }

    private static List<Integer> getLast6(List<Integer> list) {
        List<Integer> result = new ArrayList<>();
        int cnt = 0;
        int pos = list.size()-1;
        while (pos>=0&&cnt<6){
            result.add(list.remove(pos));
            pos--;
            cnt++;
        }
        return result;
    }

    private static List<Integer> getFirst6(List<Integer> list) {
        List<Integer> result = new ArrayList<>();
        int cnt=0;
        while (cnt<6&&list.size()>0){
            result.add(list.remove(0));
            cnt++;
        }
        return result;
    }



    private static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readIntArr(int n) {
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = Integer.parseInt(next());
            }
            return result;
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        long nextLong() {
            return Long.parseLong(next());
        }

    }

}
