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

#define LL long long
#define lowbit(x) ((x) & -(x))
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define MID(l, r) (((l)+(r))>>1)

const int maxn = (int) 5e2 + 20;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const double eps = 1e-8;

inline int sig(double x) {return x < -eps ? -1 : x > eps;}

template < typename T > inline void read(T &x)
{
    static bool f;
    static char ch;

    f = 0;
    x = 0;
    ch = getchar();

    while(ch < '0' || '9' < ch) {if(ch == '-') f = 1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = (x << 3) + (x << 1) + (ch - '0'); ch = getchar();}

    if(f) x = -x;
}

LL fp(LL a, LL n, LL m = MOD)
{
    LL res = 1;
    while(n)
    {
        if(n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

LL gcd(LL a, LL b)
{
    if(!b) return a;
    return gcd(b, a % b);
}

LL n;
LL a[100];

void work()
{
    cin >>n;


//    for(int i = 1; i < 100; i++)
//    {
//        cout <<i <<" " <<a[i] <<endl;
//    }

    if(n < 100)
    {
        cout <<a[n] <<endl;
    }
    else
    {
        cout <<a[n % 6] + (n / 6) * (a[n % 6 + 6] - a[n % 6]) <<endl;
    }
}


int main()
{
#ifdef yukihana0416
freopen("in.txt", "r", stdin);
#endif // yukihana0416

    a[1] = 1;
    for(int i = 2; i < 100; i++)
    {
        a[i] = 0;
        for(int j = 1; j < i; j++)
        {
            a[i] = (a[i] + a[j] * j) % i;
        }
    }
    int tc = 1;
    cin >>tc;

    for(int ca = 1; ca <= tc; ca++)
    {
//        printf("Case #%d: ", ca);
        work();
    }
    return 0;
}