#include<bits/stdc++.h>
using namespace std;
int t,n,a[2000010],maxn,minn=1e9,mx,mi=1e9,sum1[2000010],sum2[2000010];
signed main(){
	cin>>t;
	while(t--){
		maxn=0,minn=1e9,mx=0,mi=1e9;
		int ans=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			mx=max(mx,a[i]),mi=min(mi,a[i]);
		}
		if(n==1){
			cout<<0<<'\n';continue;
		}
		if(n==2){
			cout<<1<<'\n';continue;
		}
		if(n==3){
			cout<<2<<'\n';continue;	
		}	
	//	cout<<mx<<" "<<mi<<'\n';
		for(int i=1;i<n;i++){
			maxn=max(maxn,a[i]);
			minn=min(minn,a[i]);
			sum1[i]=sum1[i-1]+(a[i]%2==1);
			sum2[i]=sum2[i-1]+(a[i]%2==0);
		//	cout<<maxn<<' '<<minn<<' '<<'\n';
			if((maxn-minn==i-1)&&i!=1&&((maxn==mx)||(minn==mi))){
				ans++;
			}
		//	cout<<ans<<' ';
		//	cout<<ans<<' ';
		} 
	//	cout<<'\n';
		if((a[1]==mx&&a[2]==mi)||(a[1]==mi&&a[2]==mx)){
			ans++;
		}
		if((a[1]==mi||a[1]==mx))	ans++;
		if(n&1){
			if(sum1[n/2+1]==n/2+1){
				ans++;
			}	
			else if(sum2[n/2]==n/2){
				ans++;
			}
		}
		else{
			if((sum1[n/2]==0||sum1[n/2]==n/2)){
				ans++;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}