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

public class _C {
	long mod = 1000000007;
	int a[];
	void solve() throws IOException, IllegalArgumentException, IllegalAccessException {
		int tt=in.nextInt();
		for(int z1=0;z1<tt;z1++) {
			int n=in.nextInt();
			a=in.nextIntArr(n);
			long ans=0;
			for(int i=n-1;i>=1;i--) {
				if(a[i]<a[i-1]) {
					ans+=a[i-1]-a[i];
				}
			}
			out.println(ans);
		}
	}

	public static void main(String[] args) throws IOException, IllegalArgumentException, IllegalAccessException {
		new _C();
	}

	Debug db;
	InputReader in;
	PrintWriter out;
	StringTokenizer st;

	_C() throws IOException, IllegalArgumentException, IllegalAccessException {
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		db = new Debug(System.getSecurityManager() == null);
		solve();
		out.close();
	}
	
	void rte(boolean cond) {
		if(cond) {
			int arr[]=new int[9];
			int x=arr[9];
		}
	}

	class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

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

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

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

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int arr[] = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long arr[] = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}
	}

	class Pair implements Comparable<Pair> {
		public int x;
		public int y;

		Pair(int a, int b) {
			x = a;
			y = b;
		}

		@Override
		public int compareTo(Pair arg0) {
			if (arg0.x != x)
				return x - arg0.x;
			return y - arg0.y;
		}

		@Override
		public String toString() {
			return "(" + x + ',' + y + ')';
		}
	}

	class Triple implements Comparable<Triple> {
		public int x;
		public int y;
		public int z;

		Triple(int a, int b, int c) {
			x = a;
			y = b;
			z = c;
		}

		@Override
		public int compareTo(Triple arg0) {
			if (arg0.x != x)
				return x - arg0.x;
			return y - arg0.y;
		}

		@Override
		public String toString() {
			return "(" + x + ',' + y + ',' + z + ')';
		}
	}

	class Debug {
		private boolean allowDebug;

		public Debug(boolean allowDebug) {
			this.allowDebug = allowDebug;
		}

		private void outputName(String name) {
			System.out.print(name + " = ");
		}

		public void debug(String name, Object... x) throws IllegalArgumentException, IllegalAccessException {
			outputName(name);
			debug2(name, x);
			if (x.length == 1)
				System.out.println();
		}

		public void debug2(String name, Object... x) throws IllegalArgumentException, IllegalAccessException {
			if (!allowDebug) {
				return;
			}
			if (x.length == 1) {
				Object y = x[0];
				if (y instanceof Collection<?>) {
					ts((Iterable<Object>) y);
				} else if (y.getClass().isArray()) {
					if(y instanceof int[]) {
						System.out.print(Arrays.toString((int[]) y));
					}else if(y instanceof long[]) {
						System.out.print(Arrays.toString((long[]) y));
					}else if(y instanceof char[]) {
						System.out.print(Arrays.toString((char[]) y));
					}else if(y instanceof double[]) {
						System.out.print(Arrays.toString((double[]) y));
					}else if(y instanceof boolean[]) {
						System.out.print(Arrays.toString((boolean[]) y));
					}
					try {
//						return ts((Object[]) y);
					}catch(ClassCastException e1) {
//						return y.toString();
					}
				} else {
					System.out.print(y);
				}
			} else {
				System.out.print("[");
				for (int i = 0; i < x.length; i++) {
					if(i!=0)System.out.print(", ");
					this.debug2(name, x[i]);
				}
				System.out.println("]");
			}

		}

		void ts(Iterable<Object> iter) throws IllegalArgumentException, IllegalAccessException {
//			System.out.println("ITERABLE");
			System.out.print("[");
			boolean first = true;
			for (Object t : iter) {
				if (!first) {
					System.out.print(",");
				}
				first = false;
				debug2("name", t);
			}
			System.out.print("]");
		}
		
		void tmp(Object[] y) throws IllegalArgumentException, IllegalAccessException {
			System.out.print("[");
			boolean first = true;
			for (Object t : y) {
				if (!first) {
					System.out.print(",");
				}
				first = false;
				debug2("name", t);
			}
			System.out.print("]");
		}
	}
}