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.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * Accomplished using the EduTools plugin by JetBrains https://plugins.jetbrains.com/plugin/10081-edutools
 */

public class Main {

	public static void main(String[] args) throws Exception {
		try (InputUtil inputUtil = new InputUtil()) {
			int t = inputUtil.readLineAsInt();
			for (int i = 0; i < t; i++) {
				solve(inputUtil, i + 1);
			}
		}

	}

	private static void solve(InputUtil inputUtil, int t) throws Exception {
		int n = inputUtil.readLineAsInt();
		int[] array = inputUtil.readInts();
		long stepDiff = 0;
		for(int i = 1; i < n; i++) {
			stepDiff += Math.max(array[i - 1] - array[i], 0);
		}
		System.out.println(stepDiff);
	}

	public static class InputUtil implements Closeable {

		private final BufferedReader reader;

		public InputUtil() throws Exception {
			this.reader = new BufferedReader(new InputStreamReader(System.in));
		}

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


		public int readLineAsInt() throws Exception {
			return Integer.parseInt(reader.readLine().trim());
		}

		public long readLineAsLong() throws Exception {
			return Long.parseLong(reader.readLine());
		}

		public String getSpaceSeperatedInts(int[] ints) {
			return Stream.of(ints)
					.map(String::valueOf)
					.collect(Collectors.joining(" "));
		}

		public String getSpaceSeperatedBigInteger(BigInteger[] nums) {
			return Stream.of(nums)
					.map(BigInteger::toString)
					.collect(Collectors.joining(" "));
		}

		public boolean isEven(long number) {
			return number % 2 == 0;
		}

		public boolean isOdd(long number) {
			return !isEven(number);
		}

		public boolean isEven(BigInteger number) {
			return !number.testBit(1);
		}

		public boolean isOdd(BigInteger number) {
			return !isEven(number);
		}

		public int[] readInts() throws IOException {
			return toIntArray(reader.readLine());
		}

		public int[] toIntArray(String s) {
			return Stream.of(s.split("\\s"))
					.mapToInt(Integer::parseInt)
					.toArray();
		}

		public long[] readLongs() throws IOException {
			return toLongArray(reader.readLine().trim());
		}

		public String[] readStrings() throws IOException {
			return reader.readLine().split("\\s");

		}


		public long[] toLongArray(String s) {
			return Stream.of(s.split("\\s"))
					.mapToLong(Long::parseLong)
					.toArray();
		}

		public BigInteger[] readBigInts() throws IOException {
			return toBigIntArray(reader.readLine());
		}

		public BigInteger[] toBigIntArray(String s) {
			String[] nums = s.split("\\s");
			return IntStream.range(0, nums.length)
					.boxed()
					.map(index -> new BigInteger(nums[index]))
					.toArray(size -> new BigInteger[size]);

		}

		public char[] readChars() throws IOException {
			return reader.readLine().toCharArray();
		}

		public BufferedReader getReader() {
			return reader;
		}

		@Override
		public void close() throws IOException {
			reader.close();
		}

	}

	public static class Pair<K, V> {

		public K first;

		public V second;

		public Pair(K first, V second) {
			this.first = first;
			this.second = second;
		}

		public Pair() {
		}

		public K getFirst() {
			return this.first;
		}

		public V getSecond() {
			return this.second;
		}

		@Override
		public String toString() {
			return "Pair [first=" + first + ", second=" + second + "]";
		}
	}

	public static class Util {

		public static int max(int... values) {
			int maxChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				maxChamp = Math.max(maxChamp, values[i]);
			}
			return maxChamp;
		}

		public static long max(long... values) {
			long maxChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				maxChamp = Math.max(maxChamp, values[i]);
			}
			return maxChamp;
		}

		public static int min(int... values) {
			int minChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				minChamp = Math.min(minChamp, values[i]);
			}
			return minChamp;
		}


		public static long min(long... values) {
			long minChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				minChamp = Math.min(minChamp, values[i]);
			}
			return minChamp;
		}


		public static String getSpaceSeperatedInts(int[] ints) {
			return Arrays.stream(ints).mapToObj(i -> Integer.toString(i)).collect(Collectors.joining(" "));
		}

		public static String getSpaceSeperatedBigInteger(BigInteger[] nums) {
			return Stream.of(nums)
					.map(BigInteger::toString)
					.collect(Collectors.joining(" "));

		}

		public static boolean isEven(long number) {
			return number % 2 == 0;
		}

		public static boolean isOdd(long number) {
			return !isEven(number);
		}

		public static boolean isEven(BigInteger number) {
			return !number.testBit(1);
		}

		public static boolean isOdd(BigInteger number) {
			return !isEven(number);
		}

		public static int[] readInts(BufferedReader reader) throws IOException {
			return toIntArray(reader.readLine());
		}

		public static int[] toIntArray(String s) {
			return Stream.of(s.split("\\s")).mapToInt(Integer::parseInt).toArray();
		}

		public static long[] readLongs(BufferedReader reader) throws IOException {
			return toLongArray(reader.readLine());
		}

		public static long[] toLongArray(String s) {
			return Stream.of(s.split("\\s")).mapToLong(Long::parseLong).toArray();
		}

		public static BigInteger[] readBigInts(BufferedReader reader) throws IOException {
			return toBigIntArray(reader.readLine());
		}

		public static BigInteger[] toBigIntArray(String s) {
			String[] nums = s.split("\\s");
			return IntStream.range(0, nums.length)
					.boxed()
					.map(index -> new BigInteger(nums[index]))
					.toArray(size -> new BigInteger[size]);

		}

		public static int getMinIndex(int[] array) {
			return IntStream.range(0, array.length).reduce(0, (i, j) -> array[i] < array[j] ? i : array[i] > array[j] ? j : Math.min(i, j));
		}


		public static int getMaxIndex(int[] array) {
			return IntStream.range(0, array.length).reduce(0, (i, j) -> array[i] > array[j] ? i : array[i] < array[j] ? j : Math.min(i, j));
		}

		public static char[] readChars(BufferedReader reader) throws IOException {
			return reader.readLine().toCharArray();
		}

	}


}