Largest Rectangular Area In A Histogram

Given an array HEIGHTS of length N, where each element represents the height of a histogram bar and the width of each bar is 1, determine the area of the largest rectangle that can be formed within the bounds of the histogram.

Input

The first line contains a single integer 'T' representing the number of test cases.

Each test case consists of:
- The first line contains an integer 'N', the number of elements in 'HEIGHTS'.
- The second line contains 'N' space-separated integers representing the heights of the histogram bars.

Output

Output one integer per test case, the area of the largest rectangle that can be contained within the histogram.

Example

Input:
HEIGHTS = [2, 1, 5, 6, 2, 3]

Output:
10

Constraints

• 1 <= T <= 10
• 1 <= N <= 10^6
• 0 <= HEIGHTS[i] <= 10^9
• Time Limit: 1 sec

Note

The implementation function will handle the output printing. You only need to calculate and return the appropriate values.