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

#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
    int s=0,f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=1e3+10;
const int INF=1e9+10;
const ll base=1e9;
ll n;


void mul(ll &x,ll y){
    ll a=x/base,b=x%base;
    ll c=y/base,d=y%base;
    ll t=a*c%n*base%n*base%n;
    t+=a*d%n*base%n;
    t+=b*c%n*base%n;
    t+=d*a%n;
    t%=n;
    x=t;
}



ll qsm(ll x,ll k){
    ll res=1;
    while(k) {
        if(k&1) mul(res,x);
        mul(x,x);
    }
    return res;
}




ll dp[N];
int main(){
    /*dp[1]=dp[2]=1;
    rep(i,3,50) {
        rep(j,1,i-1) (dp[i]+=1ll*dp[j]*j%i)%=i;
    }
    rep(i,1,50) if(i%2==0) cout<<i<<' '<<dp[i]<<endl;puts("");*/
    rep(kase,1,rd()) {
        scanf("%I64d",&n);
        if(n==1) {
            puts("1");
            continue;
        }
        if(n&1) {
            if(n%6==1) {
                n-=n/6*2;
            } else n=n/6;
        } else {
            if(n%6==4) n--;
            else n/=2;
        }
        //ll t=Func(n);
        //if(n&1) t=t*(n+1)/2%n;
        //else t=;
        printf("%I64d\n",n);
    }
}