//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#include //#include #include using namespace std; #define rep(i,h,t) for (int i=h;i<=t;i++) #define dep(i,t,h) for (int i=t;i>=h;i--) #define ll long long #define me(x) memset(x,0,sizeof(x)) #define IL inline #define rint register int inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } char ss[1<<24],*A=ss,*B=ss; IL char gc() { return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++; } templatevoid maxa(T &x,T y) { if (y>x) x=y; } templatevoid mina(T &x,T y) { if (yvoid read(T &x) { int f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48); while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f; } const int mo=1e9+7; ll fsp(int x,int y) { if (y==1) return x; ll ans=fsp(x,y/2); ans=ans*ans%mo; if (y%2==1) ans=ans*x%mo; return ans; } struct cp { ll x,y; cp operator +(cp B) { return (cp){x+B.x,y+B.y}; } cp operator -(cp B) { return (cp){x-B.x,y-B.y}; } ll operator *(cp B) { return x*B.y-y*B.x; } int half() { return y < 0 || (y == 0 && x < 0); } }; struct re{ int a,b,c; }; const int N=3e5; int a[N],n; #define lowbit(x) (x&(-x)) struct sgt{ int a[N]; void add(int x) { while (x<=n) { a[x]++; x+=lowbit(x); } } int query(int x) { int ans=0; while(x>0) { ans+=a[x]; x-=lowbit(x); } return ans; } }S; unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); mt19937 myrand(seed); int main() { srand(time(0)^size_t(new char)); ios::sync_with_stdio(false); int T; cin>>T; while (T--) { cin>>n; uniform_int_distributiondist(1,n);//设定随机范围; rep(i,1,n) a[i]=i; rep(i,1,7*n) { int x=dist(myrand);int y=dist(myrand); swap(a[x],a[y]); } ll ans=0; rep(i,1,n) { if(a[i]!=i) ans++; } rep(i,1,n) a[i]=i; rep(i,1,3*n) { int x=dist(myrand);int y=dist(myrand); swap(a[x],a[y]); } ll ans2=0; rep(i,1,n) { if(a[i]!=i) ans2++; } ll ans3=0; rep(i,1,n) { cin>>a[i]; if(a[i]!=i) ans3++; } if (abs(ans3-ans2)