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.
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        FastReader in = new FastReader();
        test a=new test();
        a.solve(in,out);
        out.close();
    }
}
class test{
    public void solve(FastReader in, PrintWriter out) {

       int t = in.nextInt();
       while(t-->0){
           int n= in.nextInt();

           long[] a = new long[n];
           long max = Long.MIN_VALUE;
           long ans=Long.MIN_VALUE;
           a[0] = in.nextLong();
           for(int i=1;i<n;i++){
               a[i] = in.nextLong();
               ans = Math.max(ans,a[i]*a[i-1]);
           }
           out.println(ans);
       }
    }

    void printarr(long[] a){
        for(long i: a){
            System.out.print(i+" ");
        }
        System.out.println();
    }

    public boolean isPrime(long n){
        if(n==1 || n%2==0){
            return false;
        }
        for(long i=3;i*i<=n;i+=2){
            if(n%i==0)
                return false;
        }
        return true;
    }
    List<Integer> sieve(int n){
        int[] b = new int[n+1];
        Arrays.fill(b,0);
        b[0] = b[1] = 1;
        for(int i=2;i<=n;i++){
            if(b[i]==0){
                for(int j =2*i;j<=n;j+=i){
                    b[j] = 1;
                }
            }
        }
        List<Integer> l = new ArrayList<>();
        for(int i=0;i<b.length;i++){
            if(b[i]==0){
                l.add(i);
            }
        }
        return l;
    }
    List<Integer> segmentedSieve(long l , long r, List<Integer> prime){
        if(l==1)
            l++;
        int size = (int)(r-l+1);
        boolean[] b = new boolean[size];
        Arrays.fill(b,true);
        for(int i : prime){
            if(i*i<=r){
                int lim = (int)(l/i)*i;
                if(lim<l)
                    lim+=i;
                for(;lim<=r;lim+=i){
                    if (lim!=i)
                        b[(int)(lim-l)] = false;
                }
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i=0;i<b.length;i++){
            if(b[i]){
                list.add((int)(i+l));
            }
        }
        return list;
    }

    long gcd(long a, long b){
        if(b==0){
            return a;
        }
        return gcd(b,a%b);
    }

    public int BinarySearch(int[] a,int low,int high, int key){
        if(low>high){
            return -1;
        }
        int mid = low +(high-low)/2;
        if(key==a[mid]){
            return mid;
        }
        else if(key>a[mid]){
            return BinarySearch(a,mid+1,high,key);
        }
        else{
            return BinarySearch(a,low,mid-1,key);
        }
    }
}

class FastReader{
    BufferedReader br;
    StringTokenizer st;
    public FastReader(){

        br = new BufferedReader(new InputStreamReader(System.in));
    }
    String next(){
        while(st==null || !st.hasMoreElements()){
            try{
                st=new StringTokenizer(br.readLine());
            }
            catch(IOException e){
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    int nextInt(){
        return Integer.parseInt(next());
    }
    Long nextLong(){
        return Long.parseLong(next());
    }
    double nextDouble(){
        return Double.parseDouble(next());
    }
    String nextLine(){
        String str="";
        try{
            str=br.readLine();
        }
        catch(IOException e){
            e.printStackTrace();
        }
        return str;
    }
}
