#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
    static ui seed=416;
    return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 233333;
int a[2333333],n=5000;
ll calc(ll n){
    if(n<=100)return a[n];
    if(n%6==4)return n-1;
    if(n%6==1)return (2*n+1)/3;
    if(n%6==0||n%6==2)return n/2;
    return n/6;
}
int main() {
    a[1]=1;
    rep(i,2,n)rep(j,1,i-1)
        a[i]=(a[i]+1LL*j*a[j])%i;
    rep(i,1,n)assert(a[i]==calc(i));
    int T;read(T);while(T--){
        ll n;read(n);printf("%lld\n",calc(n));
    }
    /*rep(i,1,n){
        printf("%d %d %c\n",i,a[i],i==a[i]+1?'*':' ');
    }*/
    return 0;
}