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 {

    public static void main(String args[]) {
        FastIO io = new FastIO();
        int T = io.nextInt();
        for (int t = 1; t <= T; t++) {
            int N = io.nextInt();
            int[] arr = new int[N];
            arr[0] = io.nextInt();

            long ans = 0;
            for (int i = 1; i < N; i++) {
                arr[i] = io.nextInt();
                if (arr[i - 1] > arr[i]) {
                    ans += arr[i - 1] - arr[i];
                }
            }
            io.println(ans);
        }


        io.flushbuffer();
    }

    private static class FastIO {
        private static final int DEFAULT_BUFFER_SIZE = 65536;
        private static final int DEFAULT_LONG_SIZE = 20;
        private static final int DEFAULT_INT_SIZE = 11;
        private static final int DEFAULT_LINE_SIZE = 30;
        private static final int EOF = -1;

        private static final byte ASCII_n = 10;
        private static final byte ASCII_r = 13;
        private static final byte ASCII_space = 32;
        private static final byte ASCII_minus = 45;
        private static final byte ASCII_0 = 48;
        private static final byte ASCII_9 = 57;

        private final DataInputStream din;
        private final DataOutputStream dout;

        private byte[] inbuffer;
        private int inbufferpointer, bytesread;
        private byte[] outbuffer;
        private int outbufferpointer;

        private byte[] bytebuffer;
        private char[] charbuffer;

        private FastIO(int inbuffersize, int outbuffersize) {
            this.din = new DataInputStream(System.in);
            this.dout = new DataOutputStream(System.out);

            this.inbuffer = new byte[inbuffersize];
            this.inbufferpointer = 0;
            this.bytesread = 0;
            this.outbuffer = new byte[outbuffersize];
            this.outbufferpointer = 0;

            this.bytebuffer = new byte[DEFAULT_LONG_SIZE];
            this.charbuffer = new char[DEFAULT_LINE_SIZE];
        }

        private FastIO() {
            this(DEFAULT_BUFFER_SIZE, DEFAULT_BUFFER_SIZE);
        }

        private FastIO(int buffersize) {
            this(buffersize, buffersize);
        }

        private byte read() {
            if (inbufferpointer == bytesread)
                fillbuffer();
            return bytesread == EOF ? EOF : inbuffer[inbufferpointer++];
        }

        private void fillbuffer() {
            try {
                bytesread = din.read(inbuffer, inbufferpointer = 0, inbuffer.length);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        private void write(byte b) {
            if (outbufferpointer == outbuffer.length)
                flushbuffer();
            outbuffer[outbufferpointer++] = b;
        }

        private void flushbuffer() {
            if (outbufferpointer != 0) {
                try {
                    dout.write(outbuffer, 0, outbufferpointer);
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
                outbufferpointer = 0;
            }
        }

        private char nextChar() {
            byte b;
            while (isSpace(b = read()))
                ;
            return (char) b;
        }

        private String next() {
            byte b;
            while (isSpace(b = read())) {
            }
            int index = 0;
            do {
                charbuffer[index++] = (char) b;
            } while (!isSpace(b = read()));
            return new String(charbuffer, 0, index);
        }

        private String nextLine() {
            byte b;
            int index = 0;
            while (!isLine(b = read()))
                charbuffer[index++] = (char) b;
            return new String(charbuffer, 0, index);
        }

        private int nextInt() {
            byte b;
            while(isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = read();
            }
            int result = b - '0';
            while (isDigit(b = read()))
                result = result * 10 + b - '0';
            return negative ? -result : result;
        }

        private long nextLong() {
            byte b;
            while(isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = read();
            }
            long result = b - '0';
            while (isDigit(b = read()))
                result = result * 10 + b - '0';
            return negative ? -result : result;
        }

        private float nextFloat() {
            byte b;
            while (isSpace(b = read()))
                ;
            boolean negative = false;
            if (b == ASCII_minus) {
                negative = true;
                b = read();
            }
            float f = 0;
            do {
                f = f * 10 + b - ASCII_0;
            } while (isDigit(b = read()));
            int d = 1;
            b = read();
            do {
                f = f * 10 + b - ASCII_0;
                d = d * 10;
            } while (isDigit(b = read()));
            return f / d;

        }

        private void print(char c) {
            write((byte) c);
        }

        private void print(char[] c) {
            for (int i = 0; i < c.length; i++) {
                write((byte) c[i]);
            }
        }

        private void print(String s) {
            for (int i = 0; i < s.length(); i++) {
                write((byte) s.charAt(i));
            }
        }

        private void println(long i) {
            if (i == 0) {
                write(ASCII_0);
            } else {
                if (i < 0) {
                    write(ASCII_minus);
                    i = -i;
                }
                int index = 0;
                while (i > 0) {
                    bytebuffer[index++] = (byte) ((i % 10) + ASCII_0);
                    i /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
            write(ASCII_n);
        }

        private void printls(int i) {
            if (i == 0) {
                write(ASCII_0);
            } else {
                if (i < 0) {
                    write(ASCII_minus);
                    i = -i;
                }
                int index = 0;
                while (i > 0) {
                    bytebuffer[index++] = (byte) ((i % 10) + ASCII_0);
                    i /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
            write(ASCII_space);
        }

        private void print(long l) {
            if (l == 0) {
                write(ASCII_0);
            } else {
                if (l < 0) {
                    write(ASCII_minus);
                    l = -l;
                }
                int index = 0;
                while (l > 0) {
                    bytebuffer[index++] = (byte) ((l % 10) + ASCII_0);
                    l /= 10;
                }
                while (index-- > 0) {
                    write(bytebuffer[index]);
                }
            }
        }

        private boolean isLine(byte b) {
            return b == ASCII_r || b == ASCII_n || b == EOF;
        }

        private boolean isSpace(byte b) {
            return b <= ASCII_space && b >= 0;
        }

        private boolean isDigit(byte b) {
            return b >= ASCII_0 && b <= ASCII_9;
        }
    }
}