#include <bits/stdc++.h>
#define N 100011
#define lll __int128
#define ull unsigned long long
#define ppcll __builtin_popcountll
using namespace std;
int k[N],T,n,a[N],id[N];
vector<lll> w;
void gauss()
{
	int cc=0;
	for(int i=0;i<64;++i)
	{
		int id=-1;
		for(int j=i;j<w.size();++j)if(w[j]>>i&1){id=j;break;}
		// assert(~id);
		if(!~id){++cc;continue;}
		swap(w[i],w[id]);
		for(int j=0;j<w.size();++j)if(j!=i&&(w[j]>>i&1))w[j]^=w[i];
	}
	// printf("cc:%d\n",cc);
	// for(int i=0;i<w.size();++i)
	// {
	// 	for(int j=0;j<64;++j)printf("%d",int(w[i]>>j&1));putchar(10);
	// }
}
ull x[64];
void splitmix()
{
	for(int i=63;i>=13;--i)x[i]^=x[i-13];
	for(int i=0;i<=56;++i)x[i]^=x[i+7];
	for(int i=63;i>=17;--i)x[i]^=x[i-17];
}
const int W=68;
ull splitmix(ull x)
{
	x^=x<<13;
	x^=x>>7;
	x^=x<<17;
	return x;
}
bool check(ull x)
{
	static int tk[N];
	for(int i=1;i<=n;++i)
	{
		tk[i]=(x=splitmix(x))%i;
		if(tk[i]^k[i])return 0;
	}
	return 1;
}
int main()
{
	scanf("%d",&T);while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i)scanf("%d",a+i),id[a[i]]=i;
		for(int i=n;i;--i)
		{
			k[i]=id[i]-1;
			int x=id[i];
			id[a[i]]=x;
			swap(a[i],a[x]);
		}
		// for(int i=1;i<=n;++i)printf("%d ",k[i]);putchar(10);
		for(int i=0;i<64;++i)x[i]=(ull)1<<i;
		w.clear();
		if(n>W)
		{
			for(int i=1;i<=W;++i)
			{
				splitmix();
				for(int j=0;(i&(ull)(1<<j+1)-1)==0;++j)
				{
					w.push_back(x[j]|(lll)(k[i]>>j&1)<<64);
				}
			}
			gauss();
			ull ans=0;
			for(int i=0;i<64;++i)if(w[i]>>64&1)ans|=(ull)1<<i;
			printf("%llu\n",ans);
		}
		else
		{
			for(int i=1;i<=50;++i)
			{
				splitmix();
				for(int j=0;(i&(ull)(1<<j+1)-1)==0;++j)
				{
					w.push_back(x[j]|(lll)(k[i]>>j&1)<<64);
				}
			}
			gauss();
			for(int S=0;S<1<<19;++S)
			{
				ull K=(ull)S<<45;
				bool ok=1;
				for(int i=45;i<=46;++i)if((ppcll((ull)(K&w[i]))&1)!=(w[i]>>64&1)){ok=0;break;}
				if(!ok)continue;
				ull x=K;
				for(int i=0;i<45;++i)
				{
					int bit=(ppcll((ull)(K&w[i]))&1)^(w[i]>>64&1);
					x|=(ull)bit<<i;
				}
				if(check(x)){printf("%llu\n",x);break;}
			}
		}
	}
	fclose(stdin);fclose(stdout);return 0;
}