// Created by Pratik
// NIT PATNA

#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;

using namespace std;
#define M                    1000000007
#define pi                   3.14159265358979323846
#define ll                   long long
#define lld                  long double

// Pair
#define pii                  pair<int, int>
#define pll                  pair<ll, ll>

// Vector
#define vl                   vector<ll >
#define vi                   vector<int>
#define vpi                  vector<pii>
#define vpl                  vector<pll>
#define pb                   push_back
#define mp                   make_pair


// Search
#define lb                   lower_bound
#define ub                   upper_bound
#define mina                 *min_element
#define mama                 *max_element
#define bsrch                binary_search

////////
#define F                    first
#define S                    second
#define cel(x,a)             ((x + a - 1) / a)
#define all(v)               v.begin(), v.end()
#define allrev(v)            v.rbegin(), v.rend()
#define lcm(m, n)            ((m / __gcd(m, n))*n)
#define deb(...)             cerr << "(" << #__VA_ARGS__ << "):", dbg(__VA_ARGS__)
#define ms(arr, v)           memset(arr, v, sizeof(arr))
#define ps(x,y)              fixed << setprecision(y) << x
#define _X_                  ios_base::sync_with_stdio(false); cin.tie(NULL)

//pbds
#define ordered                 tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

// Input / Output
#define scn(str)             scanf("%s", str)
#define pri(str)             printf("%s\n", str)


const int N = 2.5e6 + 4;

inline void  dbg()           { cerr << endl; }


template <typename T, typename... V>
inline void  dbg(T t, V... v) {cerr << ' ' << t; dbg(v...);}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void solve()
{
    int n;
    cin >> n;
    vi arr(n+2),brr;
    arr[0] = 0;
    for(int i = 0; i<n; i++)cin >> arr[i+1];
    arr[n+1] = 2*n+1;
	int cur = 1;
	for(int i = 1; i<=2*n; i++)
	{
		if(cur<n+2 && arr[cur]==i)
		{
			cur++;
			continue;
		}
		brr.pb(i);
	}
	int l = 0,r = n+1;
	while(l+1<r)
	{
		int mid = (l+r)/2;
		bool ok1 = 1;
		cur = 0;
		for(int i = mid; i<n+1; i++,cur++)
		{
			if(arr[i]<brr[cur])ok1 = 0;
		}
		if(ok1)r = mid;
		else l = mid;
		//deb(ok1,ok2,l,r);
	}
	//deb(l,r);
	int mn = r;
	l = 0,r = n+1;
	while(l+1<r)
	{
		
		int mid = (l+r)/2;
		bool ok2 = 1;
		cur = n-mid;
		for(int i = 1; i<=mid; i++,cur++)
		{
			if(arr[i]>brr[cur])ok2 = 0;
		}
		if(ok2)l = mid;
		else r = mid;
		
	}
	int mx = r;
	//deb(mx,mn);
	cout << mx-mn+1 << "\n";
			
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    // clock_t time_req = clock();

    int t = 1;
     cin>> t;
    while (t--) {
       solve();



   }


    // time_req = clock() - time_req;
    // cout << (float)time_req / CLOCKS_PER_SEC;
   return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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.

### Response

```cpp
// Created by Pratik
// NIT PATNA

#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;

using namespace std;
#define M                    1000000007
#define pi                   3.14159265358979323846
#define ll                   long long
#define lld                  long double

// Pair
#define pii                  pair<int, int>
#define pll                  pair<ll, ll>

// Vector
#define vl                   vector<ll >
#define vi                   vector<int>
#define vpi                  vector<pii>
#define vpl                  vector<pll>
#define pb                   push_back
#define mp                   make_pair


// Search
#define lb                   lower_bound
#define ub                   upper_bound
#define mina                 *min_element
#define mama                 *max_element
#define bsrch                binary_search

////////
#define F                    first
#define S                    second
#define cel(x,a)             ((x + a - 1) / a)
#define all(v)               v.begin(), v.end()
#define allrev(v)            v.rbegin(), v.rend()
#define lcm(m, n)            ((m / __gcd(m, n))*n)
#define deb(...)             cerr << "(" << #__VA_ARGS__ << "):", dbg(__VA_ARGS__)
#define ms(arr, v)           memset(arr, v, sizeof(arr))
#define ps(x,y)              fixed << setprecision(y) << x
#define _X_                  ios_base::sync_with_stdio(false); cin.tie(NULL)

//pbds
#define ordered                 tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

// Input / Output
#define scn(str)             scanf("%s", str)
#define pri(str)             printf("%s\n", str)


const int N = 2.5e6 + 4;

inline void  dbg()           { cerr << endl; }


template <typename T, typename... V>
inline void  dbg(T t, V... v) {cerr << ' ' << t; dbg(v...);}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void solve()
{
    int n;
    cin >> n;
    vi arr(n+2),brr;
    arr[0] = 0;
    for(int i = 0; i<n; i++)cin >> arr[i+1];
    arr[n+1] = 2*n+1;
	int cur = 1;
	for(int i = 1; i<=2*n; i++)
	{
		if(cur<n+2 && arr[cur]==i)
		{
			cur++;
			continue;
		}
		brr.pb(i);
	}
	int l = 0,r = n+1;
	while(l+1<r)
	{
		int mid = (l+r)/2;
		bool ok1 = 1;
		cur = 0;
		for(int i = mid; i<n+1; i++,cur++)
		{
			if(arr[i]<brr[cur])ok1 = 0;
		}
		if(ok1)r = mid;
		else l = mid;
		//deb(ok1,ok2,l,r);
	}
	//deb(l,r);
	int mn = r;
	l = 0,r = n+1;
	while(l+1<r)
	{
		
		int mid = (l+r)/2;
		bool ok2 = 1;
		cur = n-mid;
		for(int i = 1; i<=mid; i++,cur++)
		{
			if(arr[i]>brr[cur])ok2 = 0;
		}
		if(ok2)l = mid;
		else r = mid;
		
	}
	int mx = r;
	//deb(mx,mn);
	cout << mx-mn+1 << "\n";
			
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    // clock_t time_req = clock();

    int t = 1;
     cin>> t;
    while (t--) {
       solve();



   }


    // time_req = clock() - time_req;
    // cout << (float)time_req / CLOCKS_PER_SEC;
   return 0;
}

```