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.BufferedInputStream;
import java.util.Scanner;

/**
 * Accomplished using the EduTools plugin by JetBrains https://plugins.jetbrains.com/plugin/10081-edutools
 *
 * To modify the template, go to Preferences -> Editor -> File and Code Templates -> Other
 */

public class Main {
   public static void main(String[] args) {
      // Write your solution here
      Scanner scanner = new Scanner(new BufferedInputStream(System.in));
      int[] a_s = new int[100005];
      int t = scanner.nextInt();

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

         for (int i = 0; i < n; i++) {
            a_s[i] = scanner.nextInt();
         }

         int l, h;

         long max = 0;

         if (a_s[0] < a_s[1]) {
            l = 0; h = 1;
         } else {
            l = 1; h = 0;
         }

         max = (long) a_s[l] * a_s[h];

         for (int i = 2; i < n; i++) {
            if (a_s[i] <= a_s[l]) {
               if (i + 1 >= n) {
                  break;
               } else {
                  if (a_s[i] < a_s[i + 1]) {
                     l = i; h = i + 1;
                  } else {
                     l = i + 1; h = i;
                  }
                  i++;
                  max = (long) a_s[l] * a_s[h] > max ? (long) a_s[l] * a_s[h] : max;
               }
            } else if (a_s[i] >= a_s[h]) {
               if (l < h) {
                  l = h;
               }
               h = i;
               max = (long) a_s[l] * a_s[h];
            } else {
               if (l < h) {
                  l = i;
                  max = (long) a_s[l] * a_s[h];
               } else {
                  if (i + 1 >= n) {
                     break;
                  } else {
                     if (a_s[i] < a_s[i + 1]) {
                        l = i; h = i + 1;
                     } else {
                        l = i + 1; h = i;
                     }
                     i++;
                     max = (long) a_s[l] * a_s[h] > max ? (long) a_s[l] * a_s[h] : max;
                  }
//                  h = i;
//                  max = (long) a_s[l] * a_s[h] > max ? (long) a_s[l] * a_s[h] : max;
               }
            }
         }

         System.out.println(max);
      }
   }
}