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.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class TaskA {

  static class Solver implements Runnable {

    int t, n;
    InputReader in;
    PrintWriter out;

    void solve() throws IOException {
      t = in.nextInt();

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

        long[] arr = in.nextLongArray(n);
        long max = 0;

        for (int i = 1; i < n; i++) {
          max = Math.max(max, arr[i] * arr[i - 1]);
        }

        out.println(max);
      }
    }

    public Solver(InputReader in, PrintWriter out) {
      this.in = in;
      this.out = out;
    }

    @Override
    public void run() {
      try {
        solve();
      } catch (IOException e) {
        e.printStackTrace();
      }
    }

  }

  static class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
        }

      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
          if (numChars <= 0) {
              return -1;
          }
      }

      return buf[curChar++];
    }

    public int nextInt() {
      int c = read();

        while (isSpaceChar(c)) {
            c = read();
        }

      int sgn = 1;

      if (c == '-') {
        sgn = -1;
        c = read();
      }

      int res = 0;

      do {
          if (c < '0' || c > '9') {
              throw new InputMismatchException();
          }

        res *= 10;
        res += c & 15;

        c = read();
      } while (!isSpaceChar(c));

      return res * sgn;
    }

    public int[] nextIntArray(int arraySize) {
      int array[] = new int[arraySize];

        for (int i = 0; i < arraySize; i++) {
            array[i] = nextInt();
        }

      return array;
    }

    public long nextLong() {
      int c = read();

        while (isSpaceChar(c)) {
            c = read();
        }

      int sign = 1;

      if (c == '-') {
        sign = -1;

        c = read();
      }

      long result = 0;

      do {
          if (c < '0' || c > '9') {
              throw new InputMismatchException();
          }

        result *= 10;
        result += c & 15;

        c = read();
      } while (!isSpaceChar(c));

      return result * sign;
    }

    public long[] nextLongArray(int arraySize) {
      long array[] = new long[arraySize];

        for (int i = 0; i < arraySize; i++) {
            array[i] = nextLong();
        }

      return array;
    }

    public float nextFloat() {
      float result, div;
      byte c;

      result = 0;
      div = 1;
      c = (byte) read();

        while (c <= ' ') {
            c = (byte) read();
        }

      boolean isNegative = (c == '-');

        if (isNegative) {
            c = (byte) read();
        }

      do {
        result = result * 10 + c - '0';
      } while ((c = (byte) read()) >= '0' && c <= '9');

        if (c == '.') {
            while ((c = (byte) read()) >= '0' && c <= '9') {
                result += (c - '0') / (div *= 10);
            }
        }

        if (isNegative) {
            return -result;
        }

      return result;
    }

    public double nextDouble() {
      double ret = 0, div = 1;
      byte c = (byte) read();

        while (c <= ' ') {
            c = (byte) read();
        }

      boolean neg = (c == '-');

        if (neg) {
            c = (byte) read();
        }

      do {
        ret = ret * 10 + c - '0';
      } while ((c = (byte) read()) >= '0' && c <= '9');

        if (c == '.') {
            while ((c = (byte) read()) >= '0' && c <= '9') {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg) {
            return -ret;
        }

      return ret;
    }

    public String next() {
      int c = read();

        while (isSpaceChar(c)) {
            c = read();
        }

      StringBuilder res = new StringBuilder();

      do {
        res.appendCodePoint(c);

        c = read();
      } while (!isSpaceChar(c));

      return res.toString();
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public String nextLine() {
      int c = read();

      StringBuilder result = new StringBuilder();

      do {
        result.appendCodePoint(c);

        c = read();
      } while (!isNewLine(c));

      return result.toString();
    }

    public boolean isNewLine(int c) {
      return c == '\n';
    }

    public void close() {
      try {
        stream.close();
      } catch (IOException e) {
        e.printStackTrace();
      }
    }

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

  }

  TaskA(InputStream inputStream, OutputStream outputStream) {
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    Thread thread = new Thread(null, new Solver(in, out), "Solver", 1 << 29);

    try {
      thread.start();
      thread.join();
    } catch (InterruptedException e) {
      e.printStackTrace();
    } finally {
      in.close();
      out.flush();
      out.close();
    }
  }

  public static void main(String[] args) {
    new TaskA(System.in, System.out);
  }

}
