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.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long int
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountint(x)
#define zrobits(x)      __builtin_ctzint(x)
#define mod             1000000007
#define INF             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define LCM(a,b)		((a*b)/__gcd(a,b))
#define PI              2*acos(0.0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


// If want to add duplicate values replace int with pair below
// and give the second pair value always unique in order to add duplicates in set.

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

// W,N,E,S
int dx[] = { -1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};


void c_p_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

// seive prime
void seive_prime(int N)
{
	vector<bool>prime(N + 1, true);
	vector<int>prime_no;

	prime[0] = false;
	prime[1] = false;

	for (int i = 4; i <= N; i += 2)
	{
		prime[i] = false;
	}

	for (int i = 3; i * i <= N; i += 2)
	{
		if (prime[i])
		{
			int m = i * i;

			while (m <= N)
			{
				prime[m] = false;
				m += i;
			}
		}
	}

	int i = 0;
	for (auto v : prime)
	{
		if (v)
			prime_no.push_back(i);

		i++;
	}

	// return prime_no;
}

// Primality Test
bool isPrime(int n)
{
	if (n == 2)
		return true;

	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
			return false;
	}

	return true;
}

// Modular Exponentiation
int modularExpo(int a, int b, int modVal)
{
	int res = 1;
	while (b > 0)
	{
		if (b & 1)
		{
			res = (res * a) % modVal;
		}

		b = b >> 1;
		a = (a * a) % modVal;
	}
	return (res % modVal);
}


// Euler Totient function
void find_phi(vector<int>&phi)
{
	for (int i = 1; i < phi.size(); i++)
		phi[i] = i;

	for (int i = 2; i < phi.size(); i++)
	{
		if (phi[i] == i)
		{
			for (int j = i; j < phi.size(); j += i)
			{
				phi[j] = phi[j] - (phi[j] / i);
			}
		}
	}

	// for(int i=3; i<phi.size(); i++)
	// {
	// 	phi[i]+=phi[i-1];
	// }
}



int32_t main()
{
	c_p_c();

	// int caseNo = 1;

	w(t)
	{
		int n;
		cin >> n;

		vector<int>arr(n, 0);

		for (int i = 0; i < n; i++)
		{
			cin >> arr[i];
		}

		if (n == 1)
		{
			cout << arr[0] << "\n";
			continue;
		}


		map<int, vector<int>>mp;

		for (int i = 0; i < n; i++)
		{
			mp[arr[i]].push_back(i);
		}

		int maxElem = -INF;

		for (auto v : mp)
		{
			maxElem = max(maxElem, v.first);
		}

		int ans = 0;

		for (auto v : mp[maxElem])
		{
			int op1, op2;
			op1 = op2 = 0;

			if (v - 1 >= 0)
				op1 = arr[v] * arr[v - 1];

			if (v + 1 < n)
				op2 = arr[v] * arr[v + 1];

			ans = max({op1, op2, ans});
		}

		cout << ans;



		cout << "\n";

	}













#ifndef ONLINE_JUDGE
	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
#endif


	return 0;

}