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.util.*;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.Math.max;
import java.io.*;

public class Codechef {
    static long[] mods = {1000000007, 998244353, 1000000009};
    static long mod = mods[0];
    public static MyScanner in;
    public static PrintWriter out;
    static int[][] dp;
    static ArrayList<ArrayList<Integer>> tree;
    static ArrayList<Long> primeFactor = new ArrayList<>();

    public static void main( String[] args ) throws IOException{

        in = new MyScanner();
        out = new PrintWriter(System.out);
        StringBuilder ans1=new StringBuilder();
        int test=in.nextInt();
        while(test-->0) {
            primeFactor.clear();
            //StringBuilder ans=new StringBuilder();
            int n=in.nextInt();
            long arr[]=readArrayLong(n);
            long ans=0;

            for(int i=0;i<n-1;i++){
                ans+=Math.max(0,arr[i]-arr[i+1]);
            }

            ans1.append(ans).append(System.getProperty("line.separator"));
        }

        out.println(ans1);
        out.close();

    }

    //comparator to solve according to b in descending order
    static class Pair implements Comparable<Pair>{
        private long a;
        private long b;
        public Pair(long a, long b) {
            this.a = a;
            this.b = b;
        }
        public int compareTo(Pair other) {
            //return Long.compare(this.b, other.b );		//to sort in ascending order swap the arguments in Long.compare
            return Long.compare(other.b ,this.b); 	//to sort in descending order swap the arguments in Long.compare
        }
    }

    static void printArray(long[] a) {
        StringBuilder stringBuilder=new StringBuilder();
        for(long i: a)	stringBuilder.append(i).append(" ");
        out.println(stringBuilder);
    }

    public static void sort(long[] array){
        ArrayList<Long> copy = new ArrayList<>();
        for (long i : array)
            copy.add(i);
        Collections.sort(copy);
        for(int i = 0;i<array.length;i++)
            array[i] = copy.get(i);
    }

    public static void sortDes(long[] array){
        ArrayList<Long> copy = new ArrayList<>();
        for (long i : array)
            copy.add(i);
        Collections.sort(copy);
        int j=array.length-1;
        for(int i = 0;i<array.length;i++)
            array[j--] = copy.get(i);
    }


    static String[] readArrayString(int n){
        String[] array = new String[n];
        for(int j =0 ;j<n;j++)
            array[j] = in.next();
        return array;
    }


    static int[] readArrayInt(int n){
        int[] array = new int[n];
        for(int j = 0;j<n;j++)
            array[j] = in.nextInt();
        return array;
    }

    static int[] readArrayInt1(int n){
        int[] array = new int[n+1];
        for(int j = 1;j<=n;j++){
            array[j] = in.nextInt();
        }
        return array;
    }

    static long[] readArrayLong(int n){
        long[] array = new long[n];
        for(int j =0 ;j<n;j++)
            array[j] = in.nextLong();
        return array;
    }

    static double[] readArrayDouble(int n){
        double[] array = new double[n];
        for(int j =0 ;j<n;j++)
            array[j] = in.nextDouble();
        return array;
    }

    static int maxIndex(long[] array){
        long maxValue = Long.MIN_VALUE;
        int maxIndex = -1;
        for(int j = 0;j<array.length;j++){
            if (array[j] > maxValue){
                maxValue = array[j];
                maxIndex = j;
            }
        }
        return maxIndex;
    }

    static int maxIndex(int[] array){
        int maxValue = Integer.MIN_VALUE;
        int maxIndex = -1;
        for(int j = 0;j<array.length;j++){
            if (array[j] > maxValue){
                maxValue = array[j];
                maxIndex = j;
            }
        }
        return maxIndex;
    }

    static int minIndex(int[] array){
        int minValue = Integer.MAX_VALUE;
        int minIndex = -1;
        for(int j = 0;j<array.length;j++){
            if (array[j] < minValue){
                minValue = array[j];
                minIndex = j;
            }
        }
        return minIndex;
    }

    static int minIndex(long[] array){
        long minValue = Long.MAX_VALUE;
        int minIndex = -1;
        for(int j = 0;j<array.length;j++){
            if (array[j] < minValue){
                minValue = array[j];
                minIndex = j;
            }
        }
        return minIndex;
    }

    static int minIndex(double[] array){
        double minValue = Double.MAX_VALUE;
        int minIndex = -1;
        for(int j = 0;j<array.length;j++){
            if (array[j] < minValue){
                minValue = array[j];
                minIndex = j;
            }
        }
        return minIndex;
    }

    static boolean isPrime(int n)
    {
        if (n <= 1)		return false;
        if (n <= 3)		return true;
        if (n % 2 == 0 || n % 3 == 0)	return false;

        for (int i = 5;i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)		return false;
        return true;
    }

    public static void primeFactors(long n)
    {
        while (n%2==0)
        {
            primeFactor.add(2L);
            n /= 2;
        }
        for (long i = 3; i <= (long) Math.sqrt(n); i+= 2)
        {
            while (n%i == 0)
            {
                primeFactor.add(i);
                n /= i;
            }
        }
        if (n > 2)
            primeFactor.add(n);
    }

    static long power(long x, long y){
        if (y == 0)
            return 1;
        if (y%2 == 1)
            return (x*power(x, y-1))%mod;
        return power((x*x)%mod, y/2)%mod;
    }
    static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }

    static long gcd_bin(long x, long a)	{
        if (x == 0)		return a;
        if (a == 0)		return x;
        int k;
        for (k = 0; ((x | a) & 1) == 0; ++k){
            x >>= 1;
            a >>= 1;
        }
        while ((x & 1) == 0)	x >>= 1;
        do{
            while ((a & 1) == 0)	a >>= 1;
            if (x > a){
                long temp = x;
                x = a;
                a = temp;
            }
            a = (a - x);
        } while (a != 0);
        return x << k;
    }

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
}
