#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
vector<long long> nextGreaterToLeft(vector<long long> arr, long long n) {
  stack<long long> s;
  vector<long long> ans;
  for (int i = 0; i < n; i++) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] < arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  return ans;
}
vector<long long> nextSmallerToRight(vector<long long> arr, long long n) {
  stack<long long> s;
  vector<long long> ans;
  for (long long i = n - 1; i >= 0; i--) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] > arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
vector<long long> nextSmallerToLeft(vector<long long> arr, int n) {
  stack<long long> s;
  vector<long long> ans;
  for (int i = 0; i < n; i++) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] > arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  return ans;
}
vector<long long> nextGreaterToRight(vector<long long> arr, long long n) {
  stack<long long> s;
  vector<long long> ans;
  for (int i = n - 1; i >= 0; i--) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] < arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long T = 1;
  cin >> T;
  while (T--) {
    vector<long long> v;
    long long n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      long long val;
      cin >> val;
      v.push_back(val);
    }
    vector<long long> Gleft = nextGreaterToLeft(v, n);
    vector<long long> Gright = nextGreaterToRight(v, n);
    vector<long long> Sleft = nextSmallerToLeft(v, n);
    vector<long long> Sright = nextSmallerToRight(v, n);
    long long maxi = (long long)1e-18;
    for (int i = 0; i < n; i++) {
      long long left = -1, right = -1;
      if (Gleft[i] != -1 and Sleft[i] != -1) {
        left = max(Gleft[i], Sleft[i]);
      } else if (Gleft[i] != -1) {
        left = Gleft[i];
      } else if (Sleft[i] != -1) {
        left = Sleft[i];
      }
      left = (left == -1 ? 0 : v[left]);
      if (Gright[i] != -1 and Sright[i] != -1) {
        right = min(Gright[i], Sright[i]);
      } else if (Gright[i] != -1) {
        right = Gright[i];
      } else if (Sright[i] != -1) {
        right = Sright[i];
      }
      right = (right == -1 ? 0 : v[right]);
      maxi = max(maxi, v[i] * max(left, right));
    }
    cout << maxi << endl;
  }
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
vector<long long> nextGreaterToLeft(vector<long long> arr, long long n) {
  stack<long long> s;
  vector<long long> ans;
  for (int i = 0; i < n; i++) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] < arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  return ans;
}
vector<long long> nextSmallerToRight(vector<long long> arr, long long n) {
  stack<long long> s;
  vector<long long> ans;
  for (long long i = n - 1; i >= 0; i--) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] > arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
vector<long long> nextSmallerToLeft(vector<long long> arr, int n) {
  stack<long long> s;
  vector<long long> ans;
  for (int i = 0; i < n; i++) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] > arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  return ans;
}
vector<long long> nextGreaterToRight(vector<long long> arr, long long n) {
  stack<long long> s;
  vector<long long> ans;
  for (int i = n - 1; i >= 0; i--) {
    if (s.empty())
      ans.push_back(-1);
    else {
      while (s.size() > 0 and arr[s.top()] < arr[i]) s.pop();
      if (s.empty())
        ans.push_back(-1);
      else
        ans.push_back(s.top());
    }
    s.push(i);
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long T = 1;
  cin >> T;
  while (T--) {
    vector<long long> v;
    long long n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      long long val;
      cin >> val;
      v.push_back(val);
    }
    vector<long long> Gleft = nextGreaterToLeft(v, n);
    vector<long long> Gright = nextGreaterToRight(v, n);
    vector<long long> Sleft = nextSmallerToLeft(v, n);
    vector<long long> Sright = nextSmallerToRight(v, n);
    long long maxi = (long long)1e-18;
    for (int i = 0; i < n; i++) {
      long long left = -1, right = -1;
      if (Gleft[i] != -1 and Sleft[i] != -1) {
        left = max(Gleft[i], Sleft[i]);
      } else if (Gleft[i] != -1) {
        left = Gleft[i];
      } else if (Sleft[i] != -1) {
        left = Sleft[i];
      }
      left = (left == -1 ? 0 : v[left]);
      if (Gright[i] != -1 and Sright[i] != -1) {
        right = min(Gright[i], Sright[i]);
      } else if (Gright[i] != -1) {
        right = Gright[i];
      } else if (Sright[i] != -1) {
        right = Sright[i];
      }
      right = (right == -1 ? 0 : v[right]);
      maxi = max(maxi, v[i] * max(left, right));
    }
    cout << maxi << endl;
  }
  return 0;
}

```