human
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.
Using python3 can you solve the prior task?
assistant
#Here is Python code to 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.

from sys import stdin, stdout
print = stdout.write
input = stdin.readline

class Node:
    def __init__(self, start, end, min, max):
        self.start, self.end = start, end
        self.min, self.max = min, max

    def __repr__(self):
        return f"{self.start}-{self.end} (min:{self.min}, max: {self.max})\n"

class BinaryTree:
    def __init__(self, array, length):
        self.array = [None for _ in range(self.get_msb(length)-1)] + \
                     [Node(i, i, array[i], array[i]) for i in range(length)] + \
                     [None for _ in range(self.get_msb(length)-length)]
        for i in range(len(self.array)//2-1, -1, -1):
            left = (i<<1) + 1
            right = left+1
            left, right = self.array[left], self.array[right]
            if left is None:
                continue
            else:

                start, end = left.start, left.end
                _min, _max = left.min, left.max
                if right is not None:
                    end = right.end
                    _min, _max = min(_min, right.min), max(_max, right.max)

                node = Node(start, end, _min, _max)
                self.array[i] = node
        print(str(self.array))

    def get_msb(self, n):
        if not n:
            return 0

        msb = 1

        while (n > 1):
            n = n>>1
            msb += 1

        return (1 << msb)

def solve_test():
    n = int(input())
    a = [int(x) for x in input().split()]
    _max = 0
    for i in range(n-1):
        _max = max(_max, a[i]*a[i+1])
    return _max

def main(args=None):
    tests = int(input())
    for _ in range(tests):
        print(f"{solve_test()}\n")

if __name__ == '__main__':
    main()