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.*;
import java.util.List;


/**
 * Created by Katushka on 11.03.2020.
 */
public class Main {

    static void sortArray(int[] a) {
        Random random = new Random();

        for (int i = 0; i < a.length; i++) {
            int randomPos = random.nextInt(a.length);
            int t = a[i];
            a[i] = a[randomPos];
            a[randomPos] = t;
        }
        Arrays.sort(a);
    }

    static int[] readArray(int size, InputReader in, boolean subOne) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt() + (subOne ? -1 : 0);
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }


    private static final long MOD = 1000000007;

    private static long addMod(long x, long y, long mod) {
        if (x < 0 || y < 0) {
            System.out.println();
        }
        long res = x + y;
        if (res >= mod) {
            return res - mod;
        }
        return res;
    }

    private static long subMod(long x, long y, long mod) {
        long res = x - y;
        if (res < 0) {
            return res + mod;
        }
        return res;
    }

    private static long fastPow(long x, long y, long mod) {
        if (x == 1) {
            return 1;
        }
        if (y == 0) {
            return 1;
        }
        long p = fastPow(x, y / 2, mod) % mod;
        p = p * p % mod;
        if (y % 2 == 1) {
            p = p * x % mod;
        }
        return p;
    }

    private static long inv(long x, long mod, Map<Long, Long> cache) {
        if (cache != null) {
            if (!cache.containsKey(x)) {
                cache.put(x, fastPow(x, mod - 2, mod));
            }
            return cache.get(x);
        } else {
            return fastPow(x, mod - 2, mod);
        }
    }


    public static void main(String[] args) throws FileNotFoundException {
        long start = System.currentTimeMillis();

//        InputReader in = new InputReader(new FileInputStream("test.txt"));
//        PrintWriter out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("greedy.out")));

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int t = in.nextInt();
        for (int ii = 0; ii < t; ii++) {
            int n = in.nextInt();
            int[] a = readArray(n, in, false);
            int cntLess = 0;
            int k = 1;
            int prev = 0;
            int res1 = 0;
            for (int i = 0; i < n; i++) {
                cntLess += a[i] - prev - 1;
                if (cntLess >= k) {
                    k++;
                } else {
                    res1 += 1;
                }
                prev = a[i];
            }

            int cntMore = 0;
            k = 1;
            prev = 2 * n + 1;
            int res2 = 0;
            for (int i = n - 1; i >= 0; i--) {
                cntMore += prev - a[i] - 1;
                if (cntMore >= k) {
                    k++;
                } else {
                    res2++;
                }
                prev = a[i];
            }
            out.println(Math.max(0, n + 1 - res1 - res2));
        }

//        out.println(System.currentTimeMillis() - start);
        out.close();

    }

    private static long c(int k, long[] cs) {
        if (k < 0 || k >= cs.length) {
            return 0;
        }
        return cs[k];
    }

    private static Map<Long, Long> invCache = new HashMap<>();

    private static long[] cs(int m) {
        if (m + 1 < 0) {
            return new long[0];
        }
        long[] res = new long[m + 1];

        if (res.length == 0) {
            return res;
        }
        res[0] = 1;
        for (int i = 1; i <= m; i++) {
            res[i] = res[i - 1] * (m - i + 1) % MOD * inv(i, MOD, invCache) % MOD;
        }
        return res;
    }

    public static List<List<Integer>> getPerms(int n) {
        Set<Integer> notUsed = new TreeSet<>();
        for (int i = 1; i <= n; i++) {
            notUsed.add(i);
        }
        ArrayList<List<Integer>> perms = getPerms(n, notUsed);
        for (List<Integer> perm : perms) {
            Collections.reverse(perm);
        }
        return perms;
    }

    public static ArrayList<List<Integer>> getPerms(int n, Set<Integer> notUsed) {
        if (n == 0) {
            return new ArrayList<>();
        }

        if (n == 1) {
            ArrayList<List<Integer>> res = new ArrayList<>();
            res.add(new ArrayList<>());
            res.get(0).add(notUsed.iterator().next());
            return res;
        }

        ArrayList<List<Integer>> res = new ArrayList<>();
        for (Integer num : notUsed) {
            TreeSet<Integer> s = new TreeSet<>(notUsed);
            s.remove(num);
            List<List<Integer>> resChild = getPerms(n - 1, s);
            for (List<Integer> nums : resChild) {
                nums.add(num);
            }
            res.addAll(resChild);
        }

        return res;
    }


    static class AVLTree<T> implements Iterable<T> {
        private Comparator<T> comparator;

        private class Node<T> {
            T data;
            int height;
            Node<T> left;
            Node<T> right;
            Node<T> parent;
            int size;

            public Node(T key) {
                this.data = key;
                this.size = 1;
            }

            public void setLeft(Node<T> left) {
                this.left = left;
                if (left != null) {
                    left.parent = this;
                }
            }

            public void setRight(Node<T> right) {
                this.right = right;
                if (right != null) {
                    right.parent = this;
                }
            }
        }

        private Node<T> root;

        public AVLTree(Comparator<T> comparator) {
            this.comparator = comparator;
        }

        void updateHeight(Node<T> n) {
            n.height = 1 + Math.max(height(n.left), height(n.right));
        }

        int height(Node<T> n) {
            return n == null ? -1 : n.height;
        }

        int getBalance(Node<T> n) {
            return (n == null) ? 0 : height(n.right) - height(n.left);
        }

        Node<T> rotateRight(Node<T> y) {
            Node<T> x = y.left;
            Node<T> z = x.right;
            x.setRight(y);
            y.setLeft(z);
            y.size = 1 + (z != null ? z.size : 0) + (y.right != null ? y.right.size : 0);
            x.size = 1 + y.size + (x.left != null ? x.left.size : 0);
            updateHeight(y);
            updateHeight(x);
            return x;
        }

        Node<T> rotateLeft(Node<T> y) {
            Node<T> x = y.right;
            Node<T> z = x.left;
            x.setLeft(y);
            y.setRight(z);
            y.size = 1 + (y.left != null ? y.left.size : 0) + (y.right != null ? y.right.size : 0);
            x.size = 1 + (x.right != null ? x.right.size : 0) + x.left.size;
            updateHeight(y);
            updateHeight(x);
            return x;
        }

        Node<T> rebalance(Node<T> z) {
            updateHeight(z);
            int balance = getBalance(z);
            if (balance > 1) {
                if (height(z.right.right) > height(z.right.left)) {
                    z = rotateLeft(z);
                } else {
                    z.setRight(rotateRight(z.right));
                    z = rotateLeft(z);
                }
            } else if (balance < -1) {
                if (height(z.left.left) > height(z.left.right))
                    z = rotateRight(z);
                else {
                    z.setLeft(rotateLeft(z.left));
                    z = rotateRight(z);
                }
            }
            return z;
        }

        private Node<T> insert(Node<T> node, T key) {
            if (node == null) {
                return new Node<>(key);
            } else if (comparator.compare(node.data, key) > 0) {
                Node<T> insert = insert(node.left, key);
                if (insert == null) {
                    return null;
                }
                node.setLeft(insert);
                node.size++;
            } else if (comparator.compare(node.data, key) < 0) {
                Node<T> insert = insert(node.right, key);
                if (insert == null) {
                    return null;
                }
                node.setRight(insert);
                node.size++;
            } else {
                return null;
            }
            return rebalance(node);
        }

        // TODO: NOT TESTED!!!
        private Node<T> delete(Node<T> node, T key) {
            if (node == null) {
                return null;
            } else if (comparator.compare(node.data, key) > 0) {
                Node<T> delete = delete(node.left, key);
                node.setLeft(delete);
            } else if (comparator.compare(node.data, key) < 0) {
                node.setRight(delete(node.right, key));
            } else {
                if (node.left == null || node.right == null) {
                    node = (node.left == null) ? node.right : node.left;
                } else {
                    Node<T> mostLeftChild = mostLeftChild(node.right);
                    node.data = mostLeftChild.data;
                    Node<T> delete = delete(node.right, node.data);
                    node.setRight(delete);
                }
            }
            if (node != null) {
                node.size--;
                node = rebalance(node);
            }
            return node;
        }

        private Node<T> mostLeftChild(Node<T> node) {
            if (node == null || node.left == null) {
                return node;
            }
            return mostLeftChild(node.left);
        }

        private Node<T> find(T key) {
            Node<T> current = root;
            while (current != null) {
                if (current.data == key) {
                    break;
                }
                current = comparator.compare(current.data, key) < 0 ? current.right : current.left;
            }
            return current;
        }

        void add(T newElement) {
            if (root == null) {
                root = new Node<>(newElement);
            } else {
                Node<T> node = insert(root, newElement);
                if (node != null) {
                    root = node;
                    root.parent = null;
                }
            }
        }

        // TODO: NOT TESTED!!!
        void remove(T element) {
            Node<T> node = delete(root, element);
            root = node;
            root.parent = null;
        }

        boolean contains(T element) {
            return find(element) != null;
        }

        int size() {
            return root == null ? 0 : root.size;
        }

        int lessEqualCount(T elem) {
            return lessEqualCount(elem, root);
        }

        int lessEqualCount(T elem, Node<T> node) {
            if (node == null) {
                return 0;
            }
            int result = 0;
            if (comparator.compare(node.data, elem) <= 0) {
                result++;
                if (node.left != null) {
                    result += node.left.size;
                }
                result += lessEqualCount(elem, node.right);
            } else {
                result += lessEqualCount(elem, node.left);
            }

            return result;
        }

        @Override
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                private Node<T> nextElement = mostLeftChild(root);

                @Override
                public boolean hasNext() {
                    return nextElement != null;
                }

                @Override
                public T next() {
                    if (nextElement == null) {
                        throw new NoSuchElementException();
                    }
                    Node<T> current = nextElement;
                    nextElement = successor(current);
                    return current.data;
                }
            };
        }

        Node<T> successor(Node<T> node) {
            if (node == null) {
                return null;
            } else if (node.right != null) {
                Node<T> p = node.right;
                while (p.left != null) {
                    p = p.left;
                }
                return p;
            } else {
                Node<T> p = node.parent;
                Node<T> ch = node;
                while (p != null && ch == p.right) {
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }


    }


    private static void outputArray(int[] ans, PrintWriter out) {
        StringBuilder str = new StringBuilder();
        for (long an : ans) {
            str.append(an).append(' ');
        }
        out.println(str);
        out.flush();
    }

    private static void outputArray(List<Integer> ans, PrintWriter out) {
        StringBuilder str = new StringBuilder();
        for (long an : ans) {
            str.append(an).append(' ');
        }
        out.println(str);
        out.flush();
    }


    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public String nextWord() {
            return next();
        }

        private List<Integer>[] readTree(int n) {
            List<Integer>[] result = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                result[i] = new ArrayList<>();
            }
            for (int i = 0; i < n - 1; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                result[u].add(v);
                result[v].add(u);
            }
            return result;
        }

    }
}