You are given a list of non-negative integers denoting the bar heights of a histogram. All the bars have a width of 1. You need to find the area of the largest possible rectange in the histogram.

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case the input has two lines:

• An integer ‘n’ denoting the number of histogram bars.
• n space-separated integers denoting the height of bars.

Output Format

For each test case, a line containing the area of the largest rectangle in the histogram.

Examples

Sample Input

2
8
8 2 10 12 7 0 10 8
3
1 3 2

Expected Output

21
4

Constraints

1 <= T <= 100
1 <= n <= 104
0 <= bar height <= 104