You have 2n integers 1, 2, ..., 2n. You have to redistribute these 2n elements into n pairs. After that, you choose x pairs and take minimum elements from them, and from the other n - x pairs, you take maximum elements.

Your goal is to obtain the set of numbers \\{b_1, b_2, ..., b_n\} as the result of taking elements from the pairs.

What is the number of different x-s (0 ≤ x ≤ n) such that it's possible to obtain the set b if for each x you can choose how to distribute numbers into pairs and from which x pairs choose minimum elements?

Input

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

The first line of each test case contains the integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line of each test case contains n integers b_1, b_2, ..., b_n (1 ≤ b_1 < b_2 < ... < b_n ≤ 2n) — the set you'd like to get.

It's guaranteed that the sum of n over test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print one number — the number of different x-s such that it's possible to obtain the set b.

Example

Input


3
1
1
5
1 4 5 9 10
2
3 4


Output


1
3
1

Note

In the first test case, x = 1 is the only option: you have one pair (1, 2) and choose the minimum from this pair.

In the second test case, there are three possible x-s. If x = 1, then you can form the following pairs: (1, 6), (2, 4), (3, 5), (7, 9), (8, 10). You can take minimum from (1, 6) (equal to 1) and the maximum elements from all other pairs to get set b.

If x = 2, you can form pairs (1, 2), (3, 4), (5, 6), (7, 9), (8, 10) and take the minimum elements from (1, 2), (5, 6) and the maximum elements from the other pairs.

If x = 3, you can form pairs (1, 3), (4, 6), (5, 7), (2, 9), (8, 10) and take the minimum elements from (1, 3), (4, 6), (5, 7).

In the third test case, x = 0 is the only option: you can form pairs (1, 3), (2, 4) and take the maximum elements from both of them.
import java.io.*;
import java.util.StringTokenizer;

public class Pairs2 {

    /**
     * First notice that if x = y where y <= n, then we will always try put the smallest y numbers into a min pairs.
     * Why can we always do this. let there be two pairs x = (a, b) and y = (c, d) such that a > c, but a is in a min pair and c
     * is in a max pair. We can make x = (c, b) and y = (a, d) and x is still a min pair, and y is still a max pair. So,
     * we will always pair the smallest i numbers when x = i, with the largest i numbers that are not in b
     **/

    public static void main(String[] args) throws IOException {

        FastReader reader = new FastReader();
        FastWriter writer = new FastWriter();
        int numTests = reader.readSingleInt();

        for (int i = 0; i < numTests; i++) {
            int n = reader.readSingleInt();
            int[] b = reader.readIntArray(n);
            int[] nB = new int[n];

            int start = 1;
            int index = 0;
            for(int j = 0; j<n; j++){
                for(int k = start; k<b[j]; k++){
                    nB[index] = k;
                    index++;
                }
                start = b[j]+1;
            }
            for(int k = b[n-1]+1; k<=2*n; k++){
                nB[index] = k;
                index++;
            }




            //Finding the largest suffix (length l) of b such that all of the elements in l are larger than the corresponding
            //elements in the prefix of size l of nb (index will tell us the size)
            index = n-1;
            for(int j = n-1; j>=0; j--){
                if(b[index] > nB[j]){
                    index--;
                }
            }
            int minX = index+1;

            //Finding the largest prefix (length l) of b such that all of the elements in l are smaller than the corresponding
            // elements in the suffix of size l of nb.
            index = 0;
            for(int j = 0; j<n; j++){
                if(b[index] < nB[j]){
                    index++;
                }
            }
            int maxX = index;

            int rangeX = Math.max(0, maxX-minX + 1);
            writer.writeSingleInteger(rangeX);
        }
    }




    public static void mergeSort(int[] a, int n) {
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        for (int i = 0; i < mid; i++) {
            l[i] = a[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = a[i];
        }
        mergeSort(l, mid);
        mergeSort(r, n - mid);

        merge(a, l, r, mid, n - mid);
    }


    public static void merge(int[] a, int[] l, int[] r, int left, int right) {

        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                a[k++] = l[i++];
            }
            else {
                a[k++] = r[j++];
            }
        }
        while (i < left) {
            a[k++] = l[i++];
        }
        while (j < right) {
            a[k++] = r[j++];
        }
    }


    public static class FastReader {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;


        public int readSingleInt() throws IOException {
            return Integer.parseInt(reader.readLine());
        }

        public int[] readIntArray(int numInts) throws IOException {
            int[] nums = new int[numInts];
            tokenizer = new StringTokenizer(reader.readLine());
            for(int i = 0; i<numInts; i++){
                nums[i] = Integer.parseInt(tokenizer.nextToken());
            }
            return nums;
        }

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

    }



    public static class FastWriter {

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));


        public void writeSingleInteger(int i) throws IOException {
            writer.write(Integer.toString(i));
            writer.newLine();
            writer.flush();
        }

        public void writeSingleLong(long i) throws IOException {
            writer.write(Long.toString(i));
            writer.newLine();
            writer.flush();
        }

        public void writeIntArrayWithSpaces(int[] nums) throws IOException {
            for(int i = 0; i<nums.length; i++){
                writer.write(nums[i] + " ");
            }
            writer.newLine();
            writer.flush();
        }

        public void writeIntArrayWithoutSpaces(int[] nums) throws IOException {
            for(int i = 0; i<nums.length; i++){
                writer.write(Integer.toString(nums[i]));
            }
            writer.newLine();
            writer.flush();
        }

        public void writeString(String s) throws IOException {
            writer.write(s);
            writer.newLine();
            writer.flush();
        }

    }
}

