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.awt.Desktop;

import java.io.BufferedReader;


import java.io.IOException;
import java.io.InputStreamReader;
import java.net.URI;
import java.net.URISyntaxException;
import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.Vector;



public  class codechef3 {
static class comp implements Comparator<Integer>
{

	@Override
	public int compare(Integer o1, Integer o2) {
		if(Math.abs(o1)>Math.abs(o2))
			return -1;
		else return 1;
	
	}

	
	}
	   

		 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()); 
		        } 
		  
		        String nextLine() 
		        { 
		            String str = ""; 
		            try
		            { 
		                str = br.readLine(); 
		            } 
		            catch (IOException e) 
		            { 
		                e.printStackTrace(); 
		            } 
		            return str; 
		        } 
		    } 
		 
		 public static String reverse(String s1)
		 {
			String s2="";
			int n=s1.length();
			for(int i=n-1;i>=0;i--)
			{
				s2+=s1.charAt(i);
			}
			return s2;
			 
			 
		 }
	
		 public static boolean check(long n)
		 {
			 
			 for(long i=2;i<=Math.sqrt(n);i++)
			 {
				 if(n%i==0)
					 return false;
			 }
			 return true;
			 
			 
			 
		 }
		 

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