#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e3+100;
long long n;
int dp[20];
int main(){
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);

//    freopen("rabbits.in","r",stdin);
//    freopen("rabbits.out","w",stdout);
    for(int _=(cin>>_,_);_--;){
        scanf("%I64d",&n);
        if(n<=20){
            dp[1]=1;
            for(int i=2;i<=n;i++){
                dp[i]=0;
                for(int j=1;j<i;j++){
                    dp[i]=(dp[i]+dp[j]*j)%i;
                }
            }
            cout<<dp[n]<<endl;
        }else {
            long long ans,tmp=n/6;
//            debug(n%6);
//            debug(tmp);
            if(n%6==0){
                ans=tmp*3;
            }else if(n%6==1){
                ans=(tmp)*4+1;
            }else if(n%6==2){
                ans=(tmp)*3+1;
            }else if(n%6==3){
                ans=(tmp);
            }else if(n%6==4){
                ans=(tmp)*6+3;
            }else if(n%6==5){
                ans=(tmp);
            }
            printf("%I64d\n",ans);
        }
        
    }
    return 0;
}