20pts WA on 12345678

#include <iostream>
#define N 100000008
#define M 1000006

using namespace std;

bool vis[N];
int ans[N];
int pri[M];
int pcnt;

int t;
int n;

void init() {
    vis[0] = vis[1] = true;
    for (int i = 2; i <= N; i++) {
        if (vis[i] == 0) {
            pri[++pcnt] = i;
            vis[i] = true;
            ans[i] = i;
        }
        for (int j = 1; j <= pcnt && (long long)pri[j] * i < N; j++) {
            vis[i * pri[j]] = true;
            ans[i * pri[j]] = ans[i] ^ pri[j];
            if (i % pri[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    init();
    cin >> t;
    while (t-- != 0) {
        cin >> n;
        cout << ans[n] << '\n';
    }
    return 0;
}