Description

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 100$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of supports Omkar has.

The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(0 \leq a_{i} \leq 10^9)$ — the heights of the supports.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of operations Omkar needs to perform to make his supports able to support his waterslide.

3
4
5 3 2 5
5
1 2 3 5 3
3
1 1 1

3
2
0

Note

The subarray with which Omkar performs the operation is bolded.

In the first test case:

• First operation:

  $[5, 3, \textbf{2}, 5] \to [5, 3, \textbf{3}, 5]$

• Second operation:

  $[5, \textbf{3}, \textbf{3}, 5] \to [5, \textbf{4}, \textbf{4}, 5]$

• Third operation:

  $[5, \textbf{4}, \textbf{4}, 5] \to [5, \textbf{5}, \textbf{5}, 5]$

In the third test case, the array is already nondecreasing, so Omkar does $0$ operations.