#include<bits/stdc++.h> using namespace std; long long _,n,a[400005],qj[400005][3],nmx[400005][2]; struct sss{ long long lg,tg,sm; }st[1600006]; struct ss{ long long l,r; bool operator<(const ss x)const{ return x.l<l; } }; map<ss,long long>mp; inline void up(long long i){ st[i].lg=st[i<<1].lg+st[i<<1|1].lg; st[i].sm=st[i<<1].sm+st[i<<1|1].sm; } inline void build(long long i,long long l,long long r){ if(l==r){ st[i].lg=1,st[i].tg=0,st[i].sm=0; return; } long long mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); up(i); } inline void dn(long long i){ if(st[i].tg){ st[i<<1].sm+=st[i].tg*st[i<<1].lg; st[i<<1|1].sm+=st[i].tg*st[i<<1|1].lg; st[i<<1].tg+=st[i].tg; st[i<<1|1].tg+=st[i].tg; st[i].tg=0; } } inline void ad(long long i,long long l,long long r,long long x,long long y){ if(x<=l && r<=y){ st[i].tg++; st[i].sm+=st[i].lg; return; } dn(i); long long mid=(l+r)>>1; if(x<=mid)ad(i<<1,l,mid,x,y); if(y>mid)ad(i<<1|1,mid+1,r,x,y); up(i); } inline long long q(long long i,long long l,long long r,long long x){ if(l==r){ return st[i].sm; } dn(i); long long mid=(l+r)>>1; if(x<=mid)return q(i<<1,l,mid,x); else return q(i<<1|1,mid+1,r,x); } int main(){ scanf("%lld",&_); while(_--){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } build(1,1,n); for(long long i=1;i<=n;i++){ if(a[i]!=i)ad(1,1,n,min(a[i],i),max(a[i],i)); if(i==1 || a[i]>a[nmx[i-1][0]])nmx[i][0]=i; else nmx[i][0]=nmx[i-1][0]; } for(int i=n;i>=1;i--){ if(i==n || a[i]<a[nmx[i+1][1]])nmx[i][1]=i; else nmx[i][1]=nmx[i+1][1]; } for(int i=1;i<=n;i++){ long long t=q(1,1,n,i); qj[i][0]=qj[i-1][0]; if(t==0)qj[i][0]++; } long long nmax=0; for(int i=1;i<=n;i++){ if(i==a[i]){ if(q(1,1,n,i)==2){ mp[((ss){nmx[i][0],nmx[i][1]})]++; } } else{ if(q(1,1,n,a[i])==2)mp[((ss){i,a[i]})]++; } } for(auto i:mp){ nmax=max(nmax,i.second); } printf("%lld\n",min(nmax+qj[n][0],n-2)); } }