#include<bits/stdc++.h>
#define N 
using namespace std;
long long n;
int a[10005];
inline void Rd(int &res){
    char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
    return;
}
int st[]={0,1,1,0,3,0,3};
int ad[]={0,4,3,1,6,1,3};
int main(){
    int T;
    Rd(T);
    while(T--){
        scanf("%lld",&n);
        int f=(n-1)%6+1;
        if(n==1)puts("1");
        else printf("%lld\n",(st[f]+1ll*ad[f]*((n-1)/6))%n);
    }
    return 0;
}