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

import javax.sound.midi.Synthesizer;

import java.awt.*;

public class Main {

	static long sx = 0, sy = 0, mod = (long) (1e9 + 7);
	static int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
	static ArrayList<pair>[] a;
	static ArrayList<Integer>[] g;
	static ArrayList<Integer>[] ra;
	static int[][][] dp;
	static long[] fa;
	static int[] farr;
	public static PrintWriter out = new PrintWriter(System.out);
	static ArrayList<pair> pa = new ArrayList<>();
	static StringBuilder sb = new StringBuilder();
	static boolean cycle = false;
	static long m = 998244353;
	static long[] no, col;
	static String s;
	// static long k = 0, n = 0, ans = 0;
	static long cnt;
	// static long[] dp;
	// static long[] p;
	// static long[] ans;
	// static Double[][] a = new Double[2][2];
	static Double[] x;
	static Double[] y;
	static long[] d;
	static boolean b = false;
	static int[][] par;
	static long[] v;
	static HashMap<Integer, Integer> map;
	// static ArrayList<Integer> p;
	static int time = 0;
	static int[] id;
	static HashSet<Integer>[] hm;

	static int[] intime;
	static int[] outime;
	static long[] ftree;
	static long ans = 0;

	static PriorityQueue<Integer> hm2;
	static HashSet<Integer> hm1;

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

		// Scanner scn = new Scanner(new BufferedReader(new
		// InputStreamReader(System.in)));
		Reader scn = new Reader();

		int t = scn.nextInt();
		StringBuilder sb = new StringBuilder();

		while (t-- != 0) {

			int n = scn.nextInt();

			TreeSet<Integer> hm = new TreeSet<>();

			for (int i = 1; i <= 2 * n; i++)
				hm.add(i);

			int[] a = scn.nextIntArray(n);

			for (int i : a)
				hm.remove(i);

			int max = 0;

			for (int i : a) {

				Integer val = hm.ceiling(i);

				if (val != null) {
					max++;
					hm.remove(val);
				}

				else
					break;
			}

			for (int i = 1; i <= 2 * n; i++)
				hm.add(i);

			for (int i : a)
				hm.remove(i);

			int lo = 0, hi = max;
			int ans = max;

			while (lo <= hi) {

				int mid = (lo + hi) >> 1;

				if (f(a, mid, new TreeSet<>(hm))) {
					ans = mid;
					hi = mid - 1;
				} else
					lo = mid + 1;
			}

			sb.append(max - ans + 1);
			sb.append("\n");
		}

		System.out.println(sb);

	}

	private static boolean f(int[] a, int mid, TreeSet<Integer> hm) {

		for (int i = 0; i < mid; i++)
			hm.remove(hm.floor(2 * a.length));

		for (int i = mid; i < a.length; i++) {

			Integer val = hm.floor(a[i]);

			if (val == null)
				return false;

			hm.remove(val);
		}

		return true;
	}

	// _________________________TEMPLATE_____________________________________________________________

	// public static long lcm(long x, long y) {
	//
	// return (x * y) / gcd(x, y);
	// }
	//
	// private static long gcd(long x, long y) {
	// if (x == 0)
	// return y;
	//
	// return gcd(y % x, x);
	// }
	//
	// static class comp implements Comparator<Integer> {
	//
	// @Override
	// public int compare(Integer p1, Integer p2) {
	//
	// if (!hm1.contains(p1))
	// return -1;
	// else if (!hm1.contains(p2))
	// return 1;
	// else
	// return 0;
	//
	// }
	// }
	//
	// }
	//
	// public static long pow(long a, long b) {
	//
	// if (b < 0)
	// return 0;
	//
	// if (b == 0 || b == 1)
	// return (long) Math.pow(a, b);
	//
	// if (b % 2 == 0) {
	//
	// long ret = pow(a, b / 2);
	// ret = (ret % mod * ret % mod) % mod;
	// return ret;
	// }
	//
	// else {
	// return ((pow(a, b - 1) % mod) * a % mod) % mod;
	// }
	// }

	private static class pair implements Comparable<pair> {
		int v;
		long w;

		pair(int a, long b) {

			this.v = a;
			this.w = b;

		}

		@Override
		public int compareTo(pair o) {

			return 0;
		}

		// @Override
		//
		// public int hashCode() {
		// return (int) (a * 17+);
		// }
		//
		// @Override
		//
		// public boolean equals(Object o) {
		//
		// pair p = (pair) o;
		// return this.a == p.a;
		// }
		//
		// @Override
		//
		// public String toString() {
		// return this.a + " ";
		// }

	}

	private static String reverse(String s) {

		return new StringBuilder(s).reverse().toString();
	}

	public static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

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

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

		public String readLine() throws IOException {
			byte[] buf = new byte[1000000 + 1]; // 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 nextInt() 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 nextLong() 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 nextDouble() 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 int[] nextIntArray(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) throws IOException {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLong();
			}
			return arr;
		}

		public int[][] nextInt2DArray(int m, int n) throws IOException {
			int[][] arr = new int[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++)
					arr[i][j] = nextInt();
			}
			return arr;
		}

		public long[][] nextInt2DArrayL(int m, int n) throws IOException {
			long[][] arr = new long[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++)
					arr[i][j] = nextInt();
			}
			return arr;
		}
		// kickstart - Solution
		// atcoder - Main
	}

}