#include<bits/stdc++.h>
#define inl inline
#define int long long
#define rep(i,x,y) for(int i=x;i<=(y);++i)
#define per(i,x,y) for(int i=x;i>=(y);--i)
#define fst; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e4+1e3;
int q,n,sum;
int p[N],cnt;
bool f[N];
inl void init(){
	rep(i,2,N){
		if(!f[i]) p[++cnt]=i;
		for(int j=1;j<=cnt&&p[j]*i<=N;j++){
			f[p[j]*i]=true;
			if(i%p[j]==0) break;
		}
	}
}
inl void handle(){
	int j=0;
	while(n>1){
		j++;
		if(p[j]>sqrt(n)) break;
		while(!(n%p[j])){
			sum^=p[j];
			n/=p[j];
		}
	}
	if(n>1) sum^=n;
	cout<<sum<<"\n";
}
signed main(){
	fst;
	init();
	cin>>q;
	rep(i,1,q){
		sum=0;
		cin>>n;
		handle();
	}
	return 0;
}

时间复杂度： $O(N log log N+q log^2n)$