#include<bits/stdc++.h>
#define int long
using namespace std;
int divi[100000005];
vector<int> v, num;
int t, n;
signed main(){
	scanf("%d", &t);
	while(t--){
		int k;
		scanf("%d", &k);
		num.push_back(k);
	}n = *max_element(num.begin(), num.end());
	iota(divi, divi + n + 1, 0);
	for(int i = 2; i <= n; ++i){
		if(divi[i] == i) v.push_back(i);
		for(int j: v){
			if(i * j > n) break;
			divi[i * j] = j;
			if(j % i == 0) break;
		}
	}for(int i: num){
		if(divi[i] == i){
			printf("%lld\n", i);
			continue;
		}int ans = 0;
		while(divi[i] == i){
			ans ^= divi[i];
			i /= divi[i];
		}printf("%lld\n", ans);
	}return 0;
}