Given a histogram consisting of n adjacent bars of width 1, where the height of the i-th bar is hi, compute the area of the largest rectangle that can be formed within the bounds of the histogram.

Input

T
n₁
h₁,₁ h₁,₂ … h₁,ₙ₁
n₂
h₂,₁ h₂,₂ … h₂,ₙ₂
…
n_T
h_T,₁ h_T,₂ … h_T,ₙ_T

1 ≤ T ≤ 1 000 — number of histograms

For each histogram i:

1 ≤ nᵢ ≤ 100 000 — number of bars

0 ≤ hᵢⱼ ≤ 10⁹ — height of the j-th bar

Total ∑ nᵢ over all histograms ≤ 10⁶

Output

For each histogram, print a single integer — the maximum rectangular area.

Example

For the first histogram, the largest rectangle spans bars 3–4 (heights 5 and 6): area = 2 × 5 = 10.

The second is a single bar of height 5 → area = 5.

For the third, bars 1–3 (heights 2,4,2) give area = 3 × 2 = 6, but bar 5 alone (height 10) gives 10.

Input: 3 6 2 1 5 6 2 3 1 5 5 2 4 2 1 10

Output: 10 5 10