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.
#include <bits/stdc++.h>

using namespace std;

/******************************MACROS******************************/

#define int long long
#define ld long double
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define vt vector
#define pb push_back
#define F first
#define S second
#define u_s unordered_set
#define u_m unordered_map
#define p_q priority_queue
#define m_p make_pair

/******************************TEMPLATE******************************/

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
    ~debug() { cerr << endl; }
    eni(!=) cerr << boolalpha << i; ris; }
    eni(==) ris << range(begin(i), end(i)); }
    sim, class b dor(pair < b, c > d) {
        ris << "(" << d.first << ", " << d.second << ")";
    }
    sim dor(rge<c> d) {
        *this << "[";
        for (auto it = d.b; it != d.e; ++it)
            *this << ", " + 2 * (it == d.b) << *it;
        ris << "]";
    }
#else
    sim dor(const c&) { ris; }
#endif
};
#define deb(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

/******************************ALGORITHMS******************************/

int __pow(int x, int y, int M) {int res = 1;while(y>0){if(y&1) res = (res*x)%M; y>>=1; x = (x*x)%M;}return res%M;}
int __pow(int x, int y) {int res = 1;while(y>0){if(y&1) res = (res*x); y>>=1; x = (x*x);}return res;}
int mi(int x, int M) {return __pow(x, M-2, M);}
int gcd(int a, int b) {if(b==0) return a; return gcd(b, a % b);}
int add(int a, int b, int M) {return (a+b) % M;}
int mul(int a, int b, int M) {return (a*b) % M;}
int sub(int a, int b, int M) {return (a-b+M) % M;}
int div(int a, int b, int M) {return (a*mi(b, M)) % M;}
void umax(int &a, int b) {a = max(a, b);}
void umin(int &a, int b) {a = min(a, b);}

/******************************main*code******************************/

const int N = 3e5+2, inf = 1e18, M = 998244353;

int Test, n, m, k, query;
bool ok = 1;

void test_case()
{
    cin >> n;
    vt<int> b(n);
    for(int &x:b) cin >> x;
    vt<int> rem, rem2;
    for(int i = 1, j = 0; i<=2*n; i++)
        if(i == b[j]) j++;
        else rem.pb(i);
    rem2 = rem;
    int m1 = 0, m2 = 0, last = 0;
    for(int i = 0; i<n; i++)
    {
        int in = lower_bound(all(rem), b[i]) - rem.begin();
        if(last == in)
            rem.pop_back(), m1++;
        else
            last++;
    }
    last = 0;
    reverse(all(rem2));
    //debug() << deb(rem2);
    for(int i = n-1; i>=0; i--)
    {
        int in = lower_bound(all(rem2), b[i], greater<int>()) - rem2.begin();
        if(rem2[in] > b[i])
            in++;
        if(last == in)
            rem2.pop_back();
        else
            last++, m2++;
        //debug() << deb(last) deb(rem2[in]) deb(i) deb(b[i]);
    }
    //debug() << deb(m1) deb(m2);
    cout << m2-m1+1 << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Test = 1;
    cin >> Test;
    while(Test--)
        test_case(); // I'm screamin' out, NO REGRETS
#ifndef ONLINE_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
    return 0;
}
