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.

K-Sort

Examples