Given N non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,

Given height = [2,1,5,6,2,3],

return 10.

The first line contains the number of test cases T. T test cases follow. Each case contains an integer N, followed by integers height[1],...,height[N] on the second line.

1 <= T <= 100 

1 <= N <= 100000 

1 <= height[i] <= 1000

Output T lines, one for each test case, containing the largest rectangle area.