Shohag has an integer sequence a_1, a_2, …, a_n. He can perform the following operation any number of times (possibly, zero):

  * Select any positive integer k (it can be different in different operations). 
  * Choose any position in the sequence (possibly the beginning or end of the sequence, or in between any two elements) and insert k into the sequence at this position. 
  * This way, the sequence a changes, and the next operation is performed on this changed sequence. 



For example, if a=[3,3,4] and he selects k = 2, then after the operation he can obtain one of the sequences [\underline{2},3,3,4], [3,\underline{2},3,4], [3,3,\underline{2},4], or [3,3,4,\underline{2}].

Shohag wants this sequence to satisfy the following condition: for each 1 ≤ i ≤ |a|, a_i ≤ i. Here, |a| denotes the size of a.

Help him to find the minimum number of operations that he has to perform to achieve this goal. We can show that under the constraints of the problem it's always possible to achieve this goal in a finite number of operations.

Input

The first line contains a single integer t (1 ≤ t ≤ 200) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 100) — the initial length of the sequence.

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — the elements of the sequence.

Output

For each test case, print a single integer — the minimum number of operations needed to perform to achieve the goal mentioned in the statement.

Example

Input


4
3
1 3 4
5
1 2 5 7 4
1
1
3
69 6969 696969


Output


1
3
0
696966

Note

In the first test case, we have to perform at least one operation, as a_2=3>2. We can perform the operation [1, 3, 4] → [1, \underline{2}, 3, 4] (the newly inserted element is underlined), now the condition is satisfied.

In the second test case, Shohag can perform the following operations:

[1, 2, 5, 7, 4] → [1, 2, \underline{3}, 5, 7, 4] → [1, 2, 3, \underline{4}, 5, 7, 4] → [1, 2, 3, 4, 5, \underline{3}, 7, 4].

In the third test case, the sequence already satisfies the condition.
1
39
481199252 336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 527268921 155191459 421436316 536134606 286802932 140515506 646837311 233465964 451394766

971207858


import java.util.*;
import java.lang.*;
import java.io.*;

public class A_Era {

    public static void main(String[] args) throws java.lang.Exception {
        FastReader sc = new FastReader();

        int t = sc.nextInt();

        while (t-- > 0) {

            int n = sc.nextInt();
            int[] arr = sc.readArray(n);
            int brr[] = Arrays.copyOfRange(arr, 0, n);
            Arrays.sort(brr);
            int mx = brr[n - 1];

            int count = 0;
            int x = 0;

            for (int i = 0; i < arr.length; i++) {
                if (i + 1 != arr[i]) {
                    count++;
                }

                if (arr[i] == mx) {
                    x = i;
                    break;
                }
            }
            System.out.println(mx - x - 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());
        }

        float nextFloat() {
            return Float.parseFloat(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] readArrayLong(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

    }

    public static int[] radixSort2(int[] a) {
        int n = a.length;
        int[] c0 = new int[0x101];
        int[] c1 = new int[0x101];
        int[] c2 = new int[0x101];
        int[] c3 = new int[0x101];
        for (int v : a) {
            c0[(v & 0xff) + 1]++;
            c1[(v >>> 8 & 0xff) + 1]++;
            c2[(v >>> 16 & 0xff) + 1]++;
            c3[(v >>> 24 ^ 0x80) + 1]++;
        }
        for (int i = 0; i < 0xff; i++) {
            c0[i + 1] += c0[i];
            c1[i + 1] += c1[i];
            c2[i + 1] += c2[i];
            c3[i + 1] += c3[i];
        }
        int[] t = new int[n];
        for (int v : a)
            t[c0[v & 0xff]++] = v;
        for (int v : t)
            a[c1[v >>> 8 & 0xff]++] = v;
        for (int v : a)
            t[c2[v >>> 16 & 0xff]++] = v;
        for (int v : t)
            a[c3[v >>> 24 ^ 0x80]++] = v;
        return a;
    }

    static boolean isPalindrome(String str) {

        // Pointers pointing to the beginning
        // and the end of the string
        int i = 0, j = str.length() - 1;

        // While there are characters to compare
        while (i < j) {

            // If there is a mismatch
            if (str.charAt(i) != str.charAt(j))
                return false;

            // Increment first pointer and
            // decrement the other
            i++;
            j--;
        }

        // Given string is a palindrome
        return true;
    }

    static boolean palindrome_array(int arr[], int n) {
        // Initialise flag to zero.
        int flag = 0;

        // Loop till array size n/2.
        for (int i = 0; i <= n / 2 && n != 0; i++) {

            // Check if first and last element are different
            // Then set flag to 1.
            if (arr[i] != arr[n - i - 1]) {
                flag = 1;
                break;
            }
        }

        // If flag is set then print Not Palindrome
        // else print Palindrome.
        if (flag == 1)
            return false;
        else
            return true;
    }

    static boolean allElementsEqual(int[] arr, int n) {
        int z = 0;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] == arr[i + 1]) {
                z++;
            }
        }
        if (z == n - 1) {
            return true;
        } else {
            return false;
        }

    }

    static boolean allElementsDistinct(int[] arr, int n) {
        int z = 0;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] != arr[i + 1]) {
                z++;
            }
        }
        if (z == n - 1) {
            return true;
        } else {
            return false;
        }

    }

    public static void reverse(int[] array) {

        // Length of the array
        int n = array.length;

        // Swaping the first half elements with last half
        // elements
        for (int i = 0; i < n / 2; i++) {

            // Storing the first half elements temporarily
            int temp = array[i];

            // Assigning the first half to the last half
            array[i] = array[n - i - 1];

            // Assigning the last half to the first half
            array[n - i - 1] = temp;
        }
    }

    public static void reverse_Long(long[] array) {

        // Length of the array
        int n = array.length;

        // Swaping the first half elements with last half
        // elements
        for (int i = 0; i < n / 2; i++) {

            // Storing the first half elements temporarily
            long temp = array[i];

            // Assigning the first half to the last half
            array[i] = array[n - i - 1];

            // Assigning the last half to the first half
            array[n - i - 1] = temp;
        }
    }

    static boolean isSorted(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) {
                return false;
            }
        }

        return true;
    }

    static boolean isReverseSorted(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] < a[i + 1]) {
                return false;
            }
        }

        return true;
    }

    static int[] rearrangeEvenAndOdd(int arr[], int n) {
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (arr[i] % 2 == 0) {
                list.add(arr[i]);
            }
        }

        for (int i = 0; i < n; i++) {
            if (arr[i] % 2 != 0) {
                list.add(arr[i]);
            }
        }
        int len = list.size();
        int[] array = list.stream().mapToInt(i -> i).toArray();
        return array;
    }

    static long[] rearrangeEvenAndOddLong(long arr[], int n) {
        ArrayList<Long> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (arr[i] % 2 == 0) {
                list.add(arr[i]);
            }
        }

        for (int i = 0; i < n; i++) {
            if (arr[i] % 2 != 0) {
                list.add(arr[i]);
            }
        }
        int len = list.size();
        long[] array = list.stream().mapToLong(i -> i).toArray();
        return array;
    }

    static boolean isPrime(long n) {

        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;

        // Check if number is 2
        else if (n == 2)
            return true;

        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;

        // If not, then just check the odds
        for (long i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    static int getSum(int n) {
        int sum = 0;

        while (n != 0) {
            sum = sum + n % 10;
            n = n / 10;
        }

        return sum;
    }

    static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static long gcdLong(long a, long b) {
        if (b == 0)
            return a;
        return gcdLong(b, a % b);
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static int countDigit(long n) {
        return (int) Math.floor(Math.log10(n) + 1);
    }

    static int sumFromString(String s) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                sum = sum + Character.getNumericValue(s.charAt(i));
            }
        }
        return sum;
    }

    static int[] freqCounter(int arr[]) {
        int[] fr = new int[arr.length];
        int[] fi = new int[arr.length];
        int visited = -1;
        for (int i = 0; i < arr.length; i++) {
            int count = 1;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                    // To avoid counting same element again
                    fr[j] = visited;
                }
            }
            if (fr[i] != visited)
                fr[i] = count;
        }
        for (int i = 0; i < fr.length; i++) {
            if (fr[i] != visited)
                fi[i] = fr[i];

        }
        return fi;
    }

}