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 Solution{
	static PrintWriter out=new PrintWriter(System.out);
	public static void main (String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String[] input=br.readLine().trim().split(" ");
		
		int numTestCases=Integer.parseInt(input[0]);
		while(numTestCases-->0){
		    input=br.readLine().trim().split(" ");
		    int n=Integer.parseInt(input[0]);
    		int[] arr=new int[n];
    		input=br.readLine().trim().split(" ");
    		for(int i=0;i<n;i++){
    		    arr[i]=Integer.parseInt(input[i]);
    		}
    		out.println(minSteps(arr));
		}
		
		out.flush();
		out.close();
	}
	public static long minSteps(int[] arr)
	{
		int n=arr.length;
		Stack<Integer> stack=new Stack<>();
		int[] prevGreaterIndices=new int[n];
		prevGreaterIndices[0]=-1;
		stack.push(0);
		for(int i=1;i<n;i++) {
			while(stack.isEmpty()==false && arr[stack.peek()]<=arr[i])
			{
				stack.pop();
			}
			if(stack.isEmpty()==false) {
				prevGreaterIndices[i]=stack.peek();
			}
			else {
				prevGreaterIndices[i]=-1;
			}
			stack.push(i);
		}
		long ans=0;
		int max=arr[0];
		for(int i=1;i<n;i++) {
			int prevGreaterIndex=prevGreaterIndices[i];
			if(prevGreaterIndex==-1)
			{
				continue;
			}
			int prevGreater=arr[prevGreaterIndex];
			int distance=i-prevGreaterIndex;
			if(distance==1) {
				ans+=(prevGreater-arr[i]);
			}
		}
		return ans;
	}
}