You are given an array of integers $a$ of length $n$.

You can apply the following operation any number of times (maybe, zero):

• First, choose an integer $k$ such that $1 \le k \le n$ and pay $k + 1$ coins.
• Then, choose exactly $k$ indices such that $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$.
• Then, for each $x$ from $1$ to $k$, increase $a_{i_x}$ by $1$.

Find the minimum number of coins needed to make $a$ non-decreasing. That is, $a_1 \le a_2 \le \ldots \le a_n$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

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

Output

For each test case, output a single integer — the minimum number of coins needed to make $a$ non-decreasing.

Note

In the first test case, $a$ is already sorted, so you don't have to spend any coins.

In the second test case, the optimal sequence of operations is:

• Choose $k = 2$ and the indices $2$ and $5$: $[ 2, \color{red}{1}, 4, 7, \color{red}{6} ] \rightarrow [2, 2, 4, 7, 7]$. This costs $3$ coins.

It can be proven that it is not possible to make $a$ non-decreasing by spending less than $3$ coins.

Samples

5
3
1 7 9
5
2 1 4 7 6
4
1 3 2 4
1
179
9
344 12 37 60 311 613 365 328 675

0
3
2
0
1821