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

 public class A {

	static FastReader		sc	= new FastReader();
	static PrintWriter	out	= new PrintWriter(System.out);
	
	public static void main(String[] args) throws Exception {


		int t =sc.nextInt();
		while (t-- > 0) {
			A.go();
		}
		out.flush();
		
	}
	
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Code Starts <<<<<<<<<<<<<<<<<<<<<<<<<<<<< //

	static void go() {
		int n=sc.nextInt();
		long a[]=sc.longArray(n);
		long ans=0;
		int l=0;
		long  max=-1;
		long min=Integer.MAX_VALUE;
		int maxpointer=0,minpointer=0;
		if(a[0]>a[1]) {
			maxpointer=0;
			minpointer=1;
			min=Math.min(min, a[1]);
			max=Math.max(max,a[0]);
		}else {
			maxpointer=1;
			minpointer=0;
			max=Math.max(max,a[1]);
			min=Math.min(min,a[0]);
		}
		ans=Math.max(ans,a[0]*a[1]);
		for(int r=2;r<n;r++) {
			if(a[r]>=a[minpointer]) {
				if(minpointer<maxpointer) {
					minpointer=r;
					ans=Math.max(ans,a[r]*a[maxpointer]);
				}else {
					if(a[r]<=a[maxpointer])
						minpointer=r;
				}
			}
			if(a[r]>a[maxpointer]) {
				if(maxpointer>minpointer) {
					minpointer=maxpointer;
					maxpointer=r;
					ans=Math.max(ans,a[r]*a[minpointer]);
				}else {
					maxpointer=r;
					ans=Math.max(ans,a[r]*a[minpointer]);
				}
			}
//			out.println(minpointer+" "+maxpointer);
		}
//		out.println(a[minpointer]+" "+a[maxpointer]);
		out.println(ans);
	}
	static int ways(int n) {
		if(n==4) {
			return 2;
		}else if(n<4) {
			return 1;
		}
	
		int ans=0;
		ans=ans+ways(n-1)+ways(n-4);
		if(( n-4==0)||(n-1==0)) {
			return 1;
		}
		return ans;
	}

 
	
	static class helper implements Comparable<helper>{
		int x,y;
		helper(int x,int y){
			this.x=x;
			this.y=y;
		}

		@Override
		public int compareTo(helper o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.x,o.x);
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			helper other = (helper) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}
	
	}

	static void   prints(char  a[][]) {

	for(int i=0;i<a.length;i++) {
		for(int j=0;j<a[i].length;j++) {
			out.print(a[i][j]);
		}
		out.println();
	}
}

	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Code Ends <<<<<<<<<<<<<<<<<<<<<<<<<<<<< //
	static long fact[];
	static long invfact[];
	static long ncr(int n,int k) {
		if(k<0||k>n) {
			return 0;
		}
		long x=fact[n]%mod;
		long y=invfact[k]%mod;
		long yy=invfact[n-k]%mod;
		long ans=(x*y)%mod;
		ans=(ans*yy)%mod;
		return ans;
	}
	static long gcd(long a, long b) {
		if (b==0) {
			return a;
		}return gcd(b, a%b);
	}
	
	static int	prime[]	= new int[200005];
	static int	N				= 200005;
	
	static void sieve() {
	
		for(int i=0;i<N;i++) {
			prime[i]=i;
	}
		for (int i = 2; i * i <= N; i++) {
			if (prime[i] == i) {
				prime[i]=i;
				for (int j = i; j < N; j += i) {
					prime[j] =i;
				}}}
	}
	
	
	static int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}return gcd(b, a % b);
	}
	 static void sort(int[] a) {
		ArrayList<Integer> aa = new ArrayList<>();
		for (Integer i : a) {
			aa.add(i);	}
		Collections.sort(aa);
		for (int i = 0; i < a.length; i++)
			a[i] = aa.get(i);}
	
	 static void sort(long[] a) {
		ArrayList<Long> aa = new ArrayList<>();
		for (Long i : a) {
			aa.add(i);}
		Collections.sort(aa);
		for (int i = 0; i < a.length; i++)
			a[i] = aa.get(i);
	}
	
	static int mod = (int) 1e9 + 7;
	
	static long pow(long x, long y) {
		long res = 1l;
		while (y != 0) {
			if (y % 2 == 1) {
				res = (x%mod * res%mod)%mod;
				}	y /= 2;
				x = (x%mod * x%mod)%mod;
		}
		return res%mod;
	}
	
	
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Fast IO <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< //
	
	static 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());
		}
		int[] intArray(int n) {
			int a[]=new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			return a;
		}
		long[] longArray(int n) {
			long a[]=new long[n];
			for(int i=0;i<n;i++)a[i]=sc.nextLong();
			return a;
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}	}}
