Largest Rectangle in a Histogram

You are given a histogram where the width of each bar is 1. The histogram is represented by an array of non-negative integers, where each integer represents the height of a bar. Your task is to compute the area of the largest rectangle that can be formed within the bounds of the histogram.

Consider a rectangle with height \(h\) and width \(w\). Its area is given by the formula \(\text{Area} = h \times w\). In this problem, you need to determine the maximum area of such a rectangle that fits entirely within the histogram.

The input consists of multiple test cases. For each test case, you are given the number of bars followed by the heights of the bars. Your program should calculate the largest rectangle area for each test case.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n₁
h₁₁ h₁₂ ... h₁ₙ₁
n₂
h₂₁ h₂₂ ... h₂ₙ₂
...
n_T
hT₁ hT₂ ... hTₙ_T

Here, T is the number of test cases. For each test case, the first line contains an integer n (the number of bars in the histogram), and the next line contains n space-separated non-negative integers representing the heights of the bars. Note that n may be zero, in which case the test case corresponds to an empty histogram.

outputFormat

For each test case, output a single line containing the area of the largest rectangle that can be fit inside the histogram. The result for each test case should be output on a new line to standard output (stdout).

## sample

5
6
2 1 5 6 2 3
2
2 4
7
6 2 5 4 5 1 6
1
5
5
3 3 3 3 3

10
4
12
5
15

</p>