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.
import java.io.*;
import java.util.*;

/**
    @author KhanhNguyenn
 */
 
public class B{
    static int MAXN= 300020;
    static int MOD= 1000000009;
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }
    // main solver
    static class Task{
        public void solve(InputReader in, PrintWriter out) {
            int t= in.nextInt();
            while(t-->0){
                int n= in.nextInt();
                int[] arr= new int[n];
                for(int z=0;z<n;z++){
                    arr[z]= in.nextInt();
                }
                long res=0;
                int cur=arr[0], min=arr[0];
                for(int i=1;i<n;i++){
                    if(arr[i]<=arr[i-1]){
                        min=Math.min(arr[i],min);
                    }
                    else{
                        res+= cur-min;
                        min=arr[i];
                        cur=arr[i];
                    }
                }
                res+= cur-min;
                out.println(res);

            }

        }
    }

    //seg
    static class SEG{
        Node[] tree= new Node[4*MAXN];
        Node[] lazy= new Node[4*MAXN];
        long[] presum;
        long[] arr;
        int n;

        public SEG(long[] arr, long[] presum){
            this.arr= arr;
            this.n= arr.length;
            this.presum= presum;
            build(1,0,n-1);
        }

        public void build(int i, int l, int r){
            tree[i]= new Node(); lazy[i]= new Node();
            tree[i].left= l; tree[i].right=r;
            lazy[i].left= l; lazy[i].right=r;
            if(l==r){
                tree[i].val=arr[l];
            }
            else{
                int mid= (l+r)>>1;
                build(2*i,l,mid);
                build(2*i+1,mid+1,r);
                tree[i].val= (tree[2*i].val + tree[2*i+1].val)%MOD;
                lazy[i].val=0;
            }
        }

        private void push(int i, int l, int r){
            if(lazy[i].val!=0){
                tree[i].val = (tree[i].val+lazy[i].val)%MOD;
                if(tree[i].left!= tree[i].right){
                    assert(lazy[i].left==lazy[2*i].left && lazy[i].right==lazy[2*i+1].right && lazy[2*i].left>=l);
                    // System.out.println(lazy[2*i].left+" "+l);
                    lazy[2*i].val=(lazy[2*i].val+ presum[lazy[2*i].right-l+1]-presum[lazy[2*i].left-l])%MOD;
                    lazy[2*i+1].val=(lazy[2*i+1].val+ presum[lazy[2*i+1].right-l+1]-presum[lazy[2*i+1].left-l])%MOD;
                }
                lazy[i].val=0;
            }
        }

        public void update(int i, int l , int r){
            if(r< tree[i].left || l> tree[i].right) return;
            if(l<=tree[i].left && r>= tree[i].right){
                push(i,l,r);
                tree[i].val=(tree[i].val+ presum[lazy[i].right-l+1]-presum[lazy[i].left-l+1])%MOD;
                if(tree[i].left!= tree[i].right){
                    lazy[2*i].val=(lazy[2*i].val+ presum[lazy[2*i].right-l+1]-presum[lazy[2*i].left-l])%MOD;
                    lazy[2*i+1].val=(lazy[2*i+1].val+ presum[lazy[2*i+1].right-l+1]-presum[lazy[2*i+1].left-l])%MOD;
                }
                return;
            }
            update(2*i,l,r);
            update(2*i+1,l,r);
            tree[i].val = (tree[2*i].val + tree[2*i+1].val)%MOD;
        }

        public long get(int i, int l, int r) {
            if(r<tree[i].left || l>tree[i].right) return 0;
            if(l<= tree[i].left && r>= tree[i].right){
                push(i,l,r);
                return tree[i].val+lazy[i].val;
            }
            return (get(2*i,l,r)+ get(2*i+1,l,r))%MOD;
        }
    }

    static class Node {
        long val=0;
        int left=-1, right=-1;
    }

    // fast input reader class;
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
 
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
        }
 
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        public double nextDouble(){
            return Double.parseDouble(nextToken());
        }
        public long nextLong(){
            return Long.parseLong(nextToken());
        }
    }
}