22222222 - idle

//为什么要攀登？因为山就在那里。
#include<bits/stdc++.h>
#define mrx 0x7f7f7f7f7f7f7f7f
//#define int long long
using namespace std;
inline int read(){int num=0,flag=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}return num*flag;
}
inline void write(int num){if(num<0) putchar('-'),num=-num;if(num>9) write(num/10);putchar(num%10+'0');
}
inline void print(int num){write(num);putchar('\n');
}
inline void out(int num){write(num);putchar(' ');
}
int ksm(int a,int b,int mod){int ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;
}
int _;
int n;
int dfn,prime[6000000];
bool vis[100000010];
int ans;
signed main(){for(int i=2;i<=100000000;++i){if(!vis[i]) prime[++dfn]=i;for(int j=1;j<=dfn&&(long long)prime[j]*i<=100000000;++j){vis[prime[j]*i]=1;if(!(i%prime[j])) break;}}_=read();for(int k=1;k<=_;++k){n=read();ans=0;if(!vis[n]){print(n);continue;}for(int i=1;i<=dfn&&prime[i]*prime[i]<=n;++i){while(n%prime[i]==0){ans^=prime[i];n/=prime[i];}if(!vis[n]&&n!=1){ans^=n;n=1;break;}}if(n!=1) ans^=n;print(ans);}return 0;
}