Largest Rectangle in Histogram

You are given a histogram represented by an array of positive integers, where each integer corresponds to the height of a building. The width of each building is 1. Your task is to calculate the area of the largest rectangle that can be formed in the histogram. The rectangle must be contiguous and its area is given by the formula $$\text{area} = \text{height} \times \text{width}$$.

In addition, you will be given multiple test cases. For each test case, compute the largest rectangle area that can be formed from the histogram provided.

Note: The input is read from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line contains a single integer \(T\) representing the number of test cases. For each test case:

• The first line contains an integer \(n\) representing the number of buildings in the histogram.
• The second line contains \(n\) space-separated positive integers where each integer denotes the height of a building.

All input is given via standard input (stdin).

outputFormat

For each test case, output a single line containing the area of the largest rectangle that can be formed in the given histogram. All output should be written to standard output (stdout).

## sample

2
7
6 2 5 4 5 1 6
4
2 4 6 8

12
12

</p>