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.util.*;
import java.io.*;
import java.util.stream.IntStream;

public class Main {

    static long startTime = System.currentTimeMillis();

    // for global initializations and methods starts here

    public static int pos2(int[] arr, int val){
        int left = 0,right = arr.length-1,index = -1;
        if (left <= right) {
            do {
                int mid = left + (right - left) / 2;
                if (arr[mid] < val) {
                    index  = mid;
                    left = mid + 1;
                } else
                    right = mid - 1;
            } while (left <= right);
        }
        return index ;
    }

    public static int pos1 (int[] arr, int val){
        int left = 0,right = arr.length-1,index = -1;
        if (left <= right) {
            do {
                int mid = left + (right - left) / 2;
                if (arr[mid] > val) {
                    index = mid;
                    right = mid - 1;
                } else
                    left = mid + 1;
            } while (left <= right);
        }
        return index;
    }

    // global initialisations and methods end here

    static void run(){
        boolean tc = true;
        AdityaFastIO r = new AdityaFastIO();
        //FastReader r = new FastReader();

        try (OutputStream out = new BufferedOutputStream(System.out)) {

            //long startTime = System.currentTimeMillis();

            int testcases = tc ? r.ni() : 1;
            int tcCounter = 1;
            // Hold Here Sparky------------------->>>
            // Solution Starts Here

            start : while (testcases --> 0) {

                int n = r.ni();
                int[] arr=new int[n];
                Set<Integer> set=new HashSet<>();
                {
                    int i=0;
                    while (i<n) {
                        set.add(arr[i]=r.ni());
                        i++;
                    }
                }

                int[] dp1 = new int[n];

                int counter = 0;

                {
                    int i=1;
                    while (i<=2*n) {
                        if(!set.contains(i)) dp1 [counter ++]=i;
                        i++;
                    }
                }
                counter =0;
                boolean[] countLeft = new boolean[n];
                boolean[] countRight = new boolean[n];

                {
                    int i=0;
                    while (i<n) {
                        int index = pos1 (dp1 ,arr[i]);
                        if (index == -1) {
                            break;
                        } else {
                            countLeft [i]=true;
                            counter =Math.max(counter +1,index +1);
                            if(counter ==n) break;
                        }
                        i++;
                    }
                }
                counter =n-1;

                {
                    int i=n-1;
                    while (i>=0) {
                        int index = pos2(dp1 , arr[i]);
                        if (index == -1) {
                            break;
                        } else {
                            countRight [i] = true;
                            counter  = Math.min(index - 1, counter  - 1);
                            if (counter  < 0) break;
                        }
                        i--;
                    }
                }

                int ans=0;
                if(countRight [0]) ans++;
                if(countLeft [n-1]) ans++;
                ans += IntStream.range(0, n - 1).filter(i -> countLeft[i] && countRight[i + 1]).count();

                out.write((ans + " ").getBytes());
                out.write(("\n").getBytes());

            }
            // Solution Ends Here
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static class AdityaFastIO{
        final private int BUFFER_SIZE = 1<<16;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        public BufferedReader br;
        public StringTokenizer st;

        public AdityaFastIO() {
            br = new BufferedReader(new InputStreamReader(System.in));
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public AdityaFastIO(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String word() {
            while (st == null || !st.hasMoreElements()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }

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

        public String readLine() throws IOException {
            byte[] buf = new byte[100000001]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int ni() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do { ret = ret * 10 + c - '0'; }
            while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nl() throws IOException {
            long ret = 0;byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do { ret = ret * 10 + c - '0'; }
            while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;return ret;
        }

        public double nd() throws IOException {
            double ret = 0, div = 1;byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do { ret = ret * 10 + c - '0'; }
            while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
    public static void main(String[] args) throws Exception {run();}

    static long mod = 998244353;
    static long modInv(long base, long e) {
        long result = 1;
        base %= mod;
        while (e>0) {
            if ((e & 1)>0) result = result * base % mod;
            base = base * base % mod;
            e >>= 1;
        }
        return result;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); }
        String word() {
            while (st == null || !st.hasMoreElements()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }
        String line() {
            String str = "";
            try { str = br.readLine(); }
            catch (IOException e) { e.printStackTrace(); }
            return str;
        }
        int ni() { return Integer.parseInt(word()); }
        long nl() { return Long.parseLong(word()); }
        double nd() { return Double.parseDouble(word()); }
    }

    static int MOD = (int) (1e9 + 7);

    static long powerLL(long x, long n) {
        long result = 1;
        while (n > 0) {
            if (n % 2 == 1) result = result * x % MOD;
            n = n / 2;x = x * x % MOD;
        }
        return result;
    }

    static long powerStrings(int i1, int i2) {
        String sa = String.valueOf(i1);
        String sb = String.valueOf(i2);
        long a = 0, b = 0;
        for (int i = 0; i < sa.length(); i++) a = (a * 10 + (sa.charAt(i) - '0')) % MOD;
        for (int i = 0; i < sb.length(); i++) b = (b * 10 + (sb.charAt(i) - '0')) % (MOD - 1);
        return powerLL(a, b);
    }

    static long gcd(long a, long b) { if (a == 0) return b;else return gcd(b % a, a); }
    static long lcm(long a, long b) { return (a * b) / gcd(a, b); }

    static long lower_bound(List<Long> list, long k) {
        int s = 0;
        int e = list.size();
        while (s != e) {
            int mid = (s + e) >> 1;
            if (list.get(mid) < k) s = mid + 1;
            else e = mid;
        }
        if (s == list.size()) return -1;
        return s;
    }

    static int upper_bound(List<Long> list, long k) {
        int s = 0;
        int e = list.size();
        while (s != e) {
            int mid = (s + e) >> 1;
            if (list.get(mid) <= k) s = mid + 1;
            else e = mid;
        }
        if (s == list.size()) return -1; return s;
    }

    static void addEdge(ArrayList<ArrayList<Integer>> graph, int edge1, int edge2) {
        graph.get(edge1).add(edge2);graph.get(edge2).add(edge1);
    }

    public static class Pair implements Comparable<Pair> {
        int first;int second;
        public Pair(int first, int second) { this.first = first;this.second = second; }
        public String toString() { return "(" + first + "," + second + ")"; }
        public int compareTo(Pair o) {
            // TODO Auto-generated method stub
            if(this.first!=o.first)
                return (int) (this.first - o.first);
            else return(int)(this.second-o.second);
        }
    }

    public static class PairC<X,Y> implements Comparable<PairC> {
        X first;Y second;
        public PairC(X first, Y second) { this.first = first;this.second = second; }
        public String toString() { return "(" + first + "," + second + ")"; }
        public int compareTo(PairC o) {
            // TODO Auto-generated method stub
            return o.compareTo((PairC) first);
        }
    }

    static boolean isCollectionsSorted(List<Long> list) {
        if (list.size() == 0 || list.size() == 1) return true;
        for (int i = 1; i < list.size(); i++) if (list.get(i) <= list.get(i - 1)) return false;
        return true;
    }

    static boolean isCollectionsSortedReverseOrder(List<Long> list) {
        if (list.size() == 0 || list.size() == 1) return true;
        for (int i = 1; i < list.size(); i++) if (list.get(i) >= list.get(i - 1)) return false;
        return true;
    }

}