Vào ngày ~9.9~, hệ thống thương mại điện tử Taka đã thông báo một chương trình khuyến mãi đặc biệt.

Chương trình sẽ cho người mua một dãy ~n~ món hàng được sắp xếp thành một đường thẳng. Người mua được phép lựa chọn một đoạn con ~[l, r]~ ~(1 \le l < r \le n)~, và mua tất cả món hàng thuộc đoạn con đó. Khi đó, người mua sẽ được hệ thống thưởng một voucher trị giá ~max(a_l, a_{l+1}, ..., a_r).min(a_l, a_{l+1}, ..., a_r)~ .

Vì là một người tiêu dùng thông minh, bạn hãy tìm giá trị voucher lớn nhất có thể được thưởng khi tham gia đợt khuyến mãi này.

Input

Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 10^4)~ là số lượng câu hỏi.

Trong mỗi câu hỏi:

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, ..., a_n~ ~(1 \le a_i \le 10^6)~.

Dữ liệu vào đảm bảo tổng các giá trị ~n~ trong tất cả câu hỏi không vượt quá ~3.10^5~.

Giới hạn

• Subtask ~1~: ~33\%~ số điểm có ~n \le 100~.
• Subtask ~2~: ~67\%~ số điểm còn lại không có ràng buộc gì thêm.

Output

Với mỗi câu hỏi, in ra một số nguyên là giá trị voucher lớn nhất có thể được thưởng trong câu hỏi đó.

Sample Input

4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

Sample Output

12
6
4761
381274500335

Giải thích

Gọi ~f(l,r)=max(a_l,a_{l+1},…,a_r)⋅min(a_l,a_{l+1},…,a_r)~.

Trong câu hỏi đầu tiên:

• ~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~.

Vậy giá trị lớn nhất là ~f(2,3)=12~.

Trong câu hỏi thứ hai, giá trị lớn nhất là ~f(1,2)=f(1,3)=f(2,3)=6~.