Xorstanta

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while(t--)
    {
        int n;
        cin >> n;

        int ans = 0;

        for(int bit = 0; (1 << bit) <= n; bit++)
            {
                int fullPeriods = (n + 1) / (1 << (bit + 1));
                int partialPeriods = (n + 1) % (1 << (bit + 1));

                int ap = fullPeriods * (1 << bit);
                ap += max(0, partialPeriods -= (1 << bit));

                if(ap % 2 == 0) ans += (1 << (bit + 1));
                else ans += (1 << bit);
            }

        cout << ans << '\n';
    }

    return 0;
}