Trapping Rain Water

You are given an array of non-negative integers representing the heights of pillars where the width of each pillar is 1. Your task is to compute how much water can be trapped between the pillars after raining.

The water trapped on top of the pillar at position i is given by the formula:

\( \text{water}_i = \min\{L_i, R_i\} - \text{height}[i] \)

where:

• \(L_i = \max_{0 \leq j \leq i}\{\text{height}[j]\}\) is the highest pillar to the left of or at i, and
• \(R_i = \max_{i \leq j \leq n-1}\{\text{height}[j]\}\) is the highest pillar to the right of or at i.

The total water trapped is the sum of water trapped on each pillar.

You need to process multiple test cases. Each test case starts with an integer n representing the number of pillars, followed by n space-separated non-negative integers indicating the heights of the pillars.

inputFormat

The first line of the input contains a single integer T representing the number of test cases. The description of the test cases follows.

For each test case:

1. The first line contains an integer n — the number of pillars.
2. The second line contains n space-separated non-negative integers denoting the heights of the pillars.

outputFormat

For each test case, output a single integer indicating the total amount of water trapped. Each result should be printed on a new line.

## sample

3
12
0 1 0 2 1 0 1 3 2 1 2 1
3
2 0 2
6
3 0 0 2 0 4

6
2
10

</p>