/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("avx2")
#pragma GCC optimize("unroll-loops")*/

#define ll int64_t

#include<bits/stdc++.h>
using namespace std;

const ll MAXN=1e5+5,INF=LLONG_MAX;
ll n,mod,o,k;

void solve(){
    cin>>n;

    k=2;
    mod=2;
    o=1;
    if(n%2==1) n=n/2+1;
    else n=n/2;
    while(n>1){
        if(k%2==1) o=o;
        else o=((n-1)*mod+o)%(mod*2);
        mod*=2;
        k++;
        if(n%2==1) n=n/2+1;
        else n=n/2;
    }

    cout<<o<<'\n';
}

int main()
{
    freopen("biscuits.in","r",stdin); freopen("biscuits.out","w",stdout);

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    ll t=1;
    cin>>t;
    while(t--) solve();

    return 0;
}