#include <iostream>
using namespace std;
long long xors(long long n) {
    const long long X = 1000000007;
    if (n * n < X) {
        return n % 2;
    }
    long long result = 0;
    long long j = 1;
    while (j <= n) {
        long long val = X / j;
        long long left = j;
        long long right = min(n, X / val);
        long long count = right - left + 1;
        result ^= count;
        j = right + 1;
    }
    return result;
}
int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        long long n;
        cin >> n;
        cout << xors(n) << endl;
    }
}
