%%%%

#include<iostream>
#include<cstdio>
#define ll long long 
using namespace std;
int n;
ll a[1000005];
ll ma1[1000005],mi1[1000005];
ll ma2[1000005],mi2[1000005];
bool j1[1000005],o1[1000005],j2[1000005],o2[1000005];
bool no[1000005];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){             
		int ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			no[i]=0;
			scanf("%lld",&a[i]); 
		}
		if(n==1){
			puts("0");
			continue;
		}
		ma1[0]=0;
		mi1[0]=1e9;
		j1[0]=1;
		o1[0]=1;
		for(int i=1;i<=n;++i){
			ma1[i]=max(ma1[i-1],a[i]);
			mi1[i]=min(mi1[i-1],a[i]);
			j1[i]=j1[i-1]&(a[i]&1);
	//	cout<<(!(a[i]&1))<<" "<<o1[i]<<endl;
			o1[i]=o1[i-1]&(!(a[i]&1));
		}
		mi2[n+1]=1e9;
		ma2[n+1]=0;
		j2[n+1]=1;
		o2[n+1]=1;
		for(int i=n;i>=1;--i){
			ma2[i]=max(ma2[i+1],a[i]);
			mi2[i]=min(mi2[i+1],a[i]); 
			j2[i]=j2[i+1]&(a[i]&1);
			o2[i]=o2[i+1]&(!(a[i]&1));
		}
	    if(a[1]==n&&1<n){
	    	if(ma2[2]==n-1&&mi2[2]==1) no[1]=1,ans++;
		}
		else if(a[1]==1&&1<n) if(ma2[2]==n&&mi2[2]==2) no[1]=1,ans++;
		
		if(a[n]==n){
			if(ma1[n-1]==n-1&&mi1[n-1]==1) no[n-1]=1,ans++;
		}
		else if(a[n]==1){
			if(ma1[n-1]==n&&mi1[n-1]==2) no[n-1]=1,ans++;
		}
	    for(int i=2;i<n;++i){
	    //	cout<<j1[i]<<" "<<j2[i+1]<<" "<<o1[i]<<" "<<o2[i+1]<<endl;
	    //	cout<<i<<" "<<ma1[i]<<" "<<ma2[i]<<" "<<mi1[i]<<" "<<mi2[i]<<endl;
	    	if(ma1[i]==i&&mi1[i]==1&&ma2[i+1]==n&&mi2[i+1]==i+1)   no[i]=1,ans++;
	    else 	if(ma1[i]==n&&mi1[i]==i&&ma2[i+1]==i-1&&mi2[i+1]==1)    no[i]=1,ans++;
	    	else if(j1[i]&&o2[i+1]||o1[i]&&j2[i+1])    no[i]=1,ans++;
		}
		if(a[1]==1&&a[2]==n||a[2]==1&&a[1]==n){
			if(!no[2]&&2<n) ans++;
		}
		if(a[n]==n&&a[n-1]==1||a[n]==1&&a[n-1]==n){
			if(!no[n-1]&&n-1>=1) ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
} 
/*

1 
6
6 2 3 4 1 5 
*/
/*
3
6
1 5 4 2 6 3
5
3 2 5 4 1
7
6 4 5 3 1 7 2
*/
/*
1
7
1 2 6 7 3 4 5
*/
/*
6
1 6 2 3 5 4
*/