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 FastReader scan = new FastReader();

	public static void main(String[] args) {
		
		int t = scan.nextInt();
		
		while(t--> 0) {
			int n = scan.nextInt();
			long a[] = new long[n];
			
			for(int i=0; i<n; i++) a[i] = scan.nextLong();
			
			long ans = 0;
			for(int i=1; i<n; i++) {
				ans += max(0, a[i-1]-a[i]);
			}
			
			System.out.println(ans);
			
		}
		
  }

	public static int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a%b);
	}
	
	private static long INFL = (long)1e17;

	public static long abs(long a, long b) {return Math.abs(a - b);}
	public static long min(long a, long b) {return Math.min(a, b);}
	public static long max(long a, long b) {return Math.max(a, b);}
	
	public static int abs(int a, int b) {return Math.abs(a - b);}
	public static int min(int a, int b) {return Math.min(a, b);}
	public static int max(int a, int b) {return Math.max(a, b);}
	
	// sieveOfEratosthenes 
	public static boolean[] sieve(int n) {
		boolean[] prime = new boolean[n+1];
		
		Arrays.fill(prime, true);
		prime[0] = false;
		prime[1] = false;
		
		for(int i=2; i*i<n; i++) {
			if(prime[i] == true) {				
				for(int j=i*2; j<=n; j+=i) {
					prime[j] = false;
				}
			}
		}
		
		return prime;
	}
	
	//smallestFactor function
	public static int smallestFactor(int n) {
		int i;
		for(i=2; i*i<=n; i++) {
			if(n%i == 0) 
				break;
		}
		return i;
	}
	
	//isPrime 
	public static boolean isPrime(int n) {
		boolean isPrime = true;
		for(int i=2; i*i<=n; i++) if(n % i == 0) isPrime = false;
		return isPrime;
	}

	//FastReader Class
	static class FastReader 
	{ 
		BufferedReader br; 
		StringTokenizer st; 

		public FastReader() 
		{ 
			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()); 
		} 
		
		char[] nextChar() 
		{
			return next().toCharArray();
		}

		String nextLine() 
		{ 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		} 
	} 
	
	private static long gcd(long m, long n) {
		if(isINFL(-m)) return n;
		assertion((m>=0L) && (n>=0L));
		if(m < n) return gcd(n, m);
		if(n == 0) return m;
		return gcd(n, m % n);
	}
	

	private static void assertion(boolean b) {
		if(!b) throw new AssertionError();
	}

	private static boolean isINFL(long in) {
		if((in*10L)>INFL) return true;
		else return false;
	}
	
}