Omkar is building a waterslide in his water park, and he needs your help to ensure that he does it as efficiently as possible.

Omkar currently has n supports arranged in a line, the i-th of which has height a_i. Omkar wants to build his waterslide from the right to the left, so his supports must be nondecreasing in height in order to support the waterslide. In 1 operation, Omkar can do the following: take any contiguous subsegment of supports which is nondecreasing by heights and add 1 to each of their heights. 

Help Omkar find the minimum number of operations he needs to perform to make his supports able to support his waterslide!

An array b is a subsegment of an array c if b can be obtained from c by deletion of several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

An array b_1, b_2, ..., b_n is called nondecreasing if b_i≤ b_{i+1} for every i from 1 to n-1.

Input

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

The first line of each test case contains an integer n (1 ≤ n ≤ 2 ⋅ 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 ≤ a_{i} ≤ 10^9) — the heights of the supports.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 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.

Example

Input


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


Output


3
2
0

Note

The subarray with which Omkar performs the operation is bolded.

In the first test case:

  * First operation:

[5, 3, 2, 5] → [5, 3, 3, 5]

  * Second operation:

[5, 3, 3, 5] → [5, 4, 4, 5]

  * Third operation:

[5, 4, 4, 5] → [5, 5, 5, 5]




In the third test case, the array is already nondecreasing, so Omkar does 0 operations.
#!/usr/local/bin/python3
"""
You are given an array arr of n integers.
In one operation, you can do the following:
    - Take any contiguous subarray of numbers which is monotonically increasing, and add 1 to each number.
Find the minimum number of operations you need to perform to make the entire array monotonically increasing.

Obs:
1,2,3,4,5,6,7,8,9
5,6,9,10,11,15,17
5,5,6,7,8,9,10,11

1,6,7,9,8,7,4,10,11,12

If the array were sorted:
    array has no duplicates:
        add 1 to every number until it equaled the max
    array has duplicates:
        add 1 to each group until it equaled the max
array is not sorted:
    We only need to account forthe subarray which is decreasing.

1,10,2,3,8,5,4,2,6,9


Sol:
monotonic queue?
    Decreasing queue -> first elem should be the max
    dequeue -> add the difference
    enqueue -> ignore duplicates

But the answer can also come from behind.

1,2,3,5,   3,6,7,   4,5,6,     1,2,3,...,15  1,2   => 5
 (1,5)     (3,7)    (4,6)        (1,15)      (1,2)

 (1,7), (2,6), (4,5), (1,9)
 (1,7), (7,7), (4,5), (1,9) => 5
 (1,7), (7,7), (7,7), (1,9) => 5+3
 (1,7), (7,7), (7,7), (7,9) => 5+3+6

The only thing I need is to get the min up to the previous max. 
Can I always do this without affecting the current max?
    Definitely not
        if prevMax > currMax => (prevMax, prevMax)
        otherwise => (prevMax,currMax)
        result += prevMax-currMin

(5,5) (3,3) (2,5) (7,9) (4,10)


(5,5) (3,3) (2,5)

What you actually want to do is to combine these guys.
Maybe that initial monotonic queue idea wasn't all that bad.
    But that doesn't work for the above, since that queue idea only works starting from the beginning.

Before max, the above works. After max, just get everything to max.

"""
def fast1(arr):
    tups = []
    window = []
    arrMax = float('-inf') 
    for num in arr:
        arrMax = max(arrMax, num)
        # print(num,window)
        if len(window) == 0:
            window.append(num)
        else:
            if num < window[-1]:
                # print(f'append {[window[0], window[-1]]}')
                tups.append([window[0], window[-1]])
                window = [num]
            else:
                window.append(num)
    if len(window) != 0:
        tups.append([window[0], window[-1]])
    # print(tups) 
    beforeTups = []
    afterTups = []
    for i in range(len(tups)):
        if tups[i][1] == arrMax:
            beforeTups = tups[:i+1]
            afterTups = tups[i+1:]
            break
    # print(beforeTups, afterTups)
    result = 0
    for i in range(1, len(beforeTups)):
        prevMin, prevMax = beforeTups[i-1]
        currMin, currMax = beforeTups[i]
        if prevMax > currMax: 
            beforeTups[i] = [prevMax,prevMax]
        else:
            beforeTups[i] = [prevMax,currMax]
        result += prevMax - currMin
    # result = 0
    afterTups.sort()
    for i in range(1,len(afterTups)):
        prevMin, prevMax = afterTups[i-1]
        currMin, currMax = afterTups[i]
        result += currMin-prevMin
    if len(afterTups) > 0:
        result += arrMax - afterTups[-1][0]
    return result


def fast(arr):
    result = 0
    maxSeen = float('-inf')
    for i, num in enumerate(arr):
        if num >= maxSeen:
            maxSeen = num
        else:
            if i>0 and arr[i-1]>arr[i]:
                result += arr[i-1]-num
    return result


def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        arr = list(map(int,input().split()))
        #CHANGE
        result = fast(arr)
        print(result)

def test():
    # arr = [1,2,3,5,3,6,7,4,5,6]
    # arr = [1,2,3,5,   3,6,7,   4,5,6,     1,2,3,15,  1,2]
    #                 5,6,7    7,7,7,     7,7,7,16,  15,15
    #                 2        3          6          14
    arr = [1,6,7,9,  8,  7,  4,10,11,12]
    #                9   9   9
    #                1   2   5
    f = fast(arr)
    print(f)

if __name__ == '__main__':
    main()
    # test()