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.*;

public class Main {
    static PrintWriter pw;
    static Scanner sc;
    static HashMap<Integer, Long> dp;
    static SegmentTree stree;
    static long ceildiv(long x, long y){ return (x+y-1)/y;}
    public static void main(String[] args) throws Exception {
        sc = new Scanner(System.in);
        pw = new PrintWriter(System.out);
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            int[] arr=sc.nextArr(n);
            long ans=0;
            for(int i=0; i<n-1; i++)
                ans+=Math.max(0, arr[i]-arr[i+1]);
            pw.println(ans);
        }
        pw.close();
    }
    static void change(int[] arr){
        int max=Integer.MIN_VALUE;
        for(int i=0; i<arr.length; i++)
            max=Math.max(max, arr[i]);
        for(int i=0; i<arr.length; i++)
            arr[i]=max-arr[i];
    }
    static void printArr(int[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(long[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(Integer[] arr){
        for(int i=0; i<arr.length; i++)
            pw.print(arr[i]+" ");
        pw.println();
    }
    static void printArr(char[] arr){
        for(int i=0; i<arr.length; i++)
            pw.print(arr[i]);
        pw.println();
    }
    static void printArr(ArrayList list){
        for(int i=0; i<list.size(); i++)
            pw.print(list.get(i)+" ");
        pw.println();
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public int[] nextArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++)
                arr[i] = nextInt();
            return arr;
        }
        public Integer[] nextsort(int n) throws IOException{
            Integer[] arr=new Integer[n];
            for(int i=0; i<n; i++)
                arr[i]=nextInt();
            return arr;
        }
        public Pair nextPair() throws IOException{
            return new Pair(nextInt(), nextInt());
        }
        public Pair[] nextPairArr(int n) throws IOException{
            Pair[] arr=new Pair[n];
            for(int i=0; i<n; i++)
                arr[i]=new Pair(nextInt(), nextInt());
            return arr;
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    static class Pair implements Comparable<Pair>{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
        public int hashCode() {
            return this.x*1000+this.y;
        }
        public int compareTo(Pair p){
            return this.x-p.x;
        }
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Pair p = (Pair) obj;
            return this.x==p.x && this.y==p.y;
        }
        public boolean equal(Pair p){
            if(this.x==p.x)
                return this.y==p.y;
            if(this.x==p.y)
                return this.y==p.x;
            else
                return false;
        }
        public Pair clone(){
            return new Pair(x, y);
        }
        public String toString(){
            return this.x+" "+this.y;
        }
    }
    static class Triple{
        int op, com, clos;
        public Triple(int x, int y, int z){
            this.op=x;
            this.com=y;
            this.clos=z;
        }
        public  String toString(){
            return op+" "+com+" "+clos;
        }
//        public int hashCode(){
//            return this.x*100+this.y;
//        }
//        public boolean equals(Object obj){
//            if (obj == null) {
//                return false;
//            }
//            if (this.getClass() != obj.getClass()) {
//                return false;
//            }
//            Triple t = (Triple) obj;
//            return this.x==t.x && this.y==t.y && this.z==t.z;
//        }
    }
    static class SegmentTree{
        long[] tree;
        long[] arr;
        public SegmentTree(long[] arr){
            this.arr=arr.clone();
            tree=new long[arr.length*2-1];
            build(0, 0, arr.length-1);
        }
        public void build(int i, int l, int r){
            if(l==r){
                tree[i]=arr[l];
            }else{
                int left=2*i+1, right=2*i+2;
                int mid=(l+r)/2;
                build(left, l, mid);
                build(right, mid+1, r);
                tree[i]=Math.max(tree[left], tree[right]);
            }
        }
        public int query(int node, int l, int r, int i, int j, long x){
            if(l>j || r<i)
                return -1;
            if(l==r){
                return tree[node]>x?node:-1;
            }else{
                int left=2*node+1, right=2*node+2, mid=(l+r)/2;
                int a=query(left, l, mid, i, j, x), b=query(right,mid+1, r, i, j, x);
                if(a!=-1 && tree[a]>x)
                    return a;
                return b!=-1 && tree[b]>x?b:-1;
            }
        }
//        public void update(int node, int l, int r, int i, int j, int x){
//            if(l>j || r<i)
//                return;
//            if(l>=i && r<=j){
//                tree[node]|=x;
//                lazy[node]|=x;
//            }else{
//                int left=2*node+1, right=2*node+2, mid=(l+r)/2;
//                propagate(node, left, right);
//                update(left, l, mid, i, j, x);
//                update(right, mid+1, r, i, j, x);
//                tree[node]=tree[left]&tree[right];
//            }
//        }
//        public void propagate(int i, int l, int r){
//            lazy[l]|=lazy[i];
//            lazy[r]|=lazy[i];
//            tree[l]|=lazy[i];
//            tree[r]|=lazy[i];
//            lazy[i]=0;
//        }
//        public void propagateAll(int i, int l, int r){
//            if(l==r)
//                return;
//            int left=2*i+1, right=2*i+2, mid=(l+r)/2;
//            propagate(i, left, right);
//            propagateAll(left, l, mid); propagateAll(right, mid+1, r);
//        }
//        public void or(int[] arr, int x, int node){
//            for(int i=0; i<30; i++)
//                arr[i]=(x&(1<<i))==0?arr[i]:1;
//        }
//        public int[] and(int[] a, int[] b){
//            int[] c=new int[30];
//            for(int i=0; i<30; i++)
//                c[i]=Math.min(a[i], b[i]);
//            return c;
//        }
//        public long valueOf(int[] arr){
//            long ans=0l;
//            for(int i=0; i<30; i++)
//                ans+=arr[i]*1l*(1<<i);
//            return ans;
//        }
//        public int[] toArray(int x){
//            int[] arr=new int[30];
//            for(int i=0; i<20; i++)
//                arr[i]=(x&(1<<i))==0?0:1;
//            return arr;
//        }
    }
    static class FenwickTree{
        long[] fen;
        public FenwickTree(int[] arr){
            fen=new long[arr.length+1];
        }
        public long query(int i, int j){
            return query(j)-query(i-1);
        }
        public long query(int x){
            long sum=0;
            while(x>0){
                sum+=fen[x];
                x^=x&-x;
            }
            return sum;
        }
        public void update(int i, int x){
            for(; i<fen.length; i+=i&-i)
                fen[i]+=x;
        }
    }
}