Trapping Rain Water

You are given the heights of buildings in a row. Your task is to determine how much water can be trapped after a rain. The water trapped on top of a building is determined by:

\( \text{water}[i] = \max( \min(\text{leftMax}[i],\; \text{rightMax}[i]) - \text{height}[i],\; 0 ) \)

where \( \text{leftMax}[i] \) is the maximum height to the left of building \( i \), and \( \text{rightMax}[i] \) is the maximum height to the right of building \( i \). You are required to handle multiple test cases in a single run. For each test case, calculate the total units of rain water trapped between the buildings.

Note: Use efficient methods since the input size can be large.

inputFormat

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

• The first line contains an integer \( n \) – the number of buildings.
• The second line contains \( n \) space-separated integers representing the heights of the buildings.

You need to read from stdin.

outputFormat

For each test case, output a single integer on a new line indicating the total units of water trapped. Write the answer to stdout.

## sample

3
6
0 1 0 2 1 0
4
3 0 2 0
5
0 0 0 0 0

1
2
0

</p>