#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 1e3 + 100;

ll n;
ll a[N];

int main() {
    a[1] = 1;
    for (int i = 2; i < N; i++) {
        for (int j = 1; j < i; j++)
            a[i] = (a[i] + a[j] * j) % i;
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%I64d", &n);
        if (n < 100) printf("%I64d\n", a[n]);
        else {
            ll ans = a[n % 6] + n / 6 * (a[n % 6 + 6] - a[n % 6]);
            printf("%I64d\n", ans);
        }
    }
    return 0;
}