record

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
int t,a[N],b[N];
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if (ch=='-'){
			w=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch)){
		s=(s<<1)+(s<<3)+ch-'0';
		ch=getchar();
	}
	return s*w;
}
signed main(){
	t=read();
	while(t--){
		int n;
		n=read();
		for(int i=1;i<=n;i++){
			a[i]=read();
			b[i]=0;
		}
		int x=1,ans=0;
		int l=0,r=n+1;
		bool f=0,f1=0;
		for(int i=1;i<n;i++){
			b[a[i]]=1;
			while(l<n&&b[l+1])l++;//1~i占满或i~n占满的情况
			while(r>1&&b[r-1])r--;
			if(l>1||r<n){
				x=0;
			}
			if(l==i||r==n-i+1||(i==2&&l==1&&r==n)||(i==n-2&&!b[1]&&!b[n])){
				ans++;
			//	cout<<l<<" "<<r<<" "<<i<<endl;
				continue;
			}
			//奇数位占满或偶数位占满
			if(a[1]&1){
				if((a[i]&1)&&x){
					if((i==ceil(n/2.0))){
						ans++;
					}
				}else{
					x=0;
				}
			}else{
				if(a[i]%2==0&&x){
					if(i==n/2){
						ans++;
					}
				}else{
					x=0;
				}
			}
		}
		printf("%d\n",ans);
	}
}