#include <iostream>
#include <map>
using namespace std;
#define ll long long

const int MOD = 95041567;
ll T[55], B[55], fac[10], a[10];
map<int, ll> vis;
int cnt;
void bell(int n, int mod) {
    B[0] = 1, B[1] = 1, T[0] = 1;
    for (int i = 2; i <= n; ++i) {
        T[i - 1] = B[i - 1];
        for (int j = i - 2; j >= 0; --j) T[j] = (T[j] + T[j + 1]) % mod;
        B[i] = T[0];
    }
}
ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll ret = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ret;
}
ll CRT(ll a[], ll m[], int n) {
    ll M = 1;
    for (int i = 0; i < n; ++i) M *= m[i];
    ll ret = 0;
    for (int i = 0; i < n; ++i) {
        ll x, y;
        ll tm = M / m[i];
        exgcd(tm, m[i], x, y);
        ret = (ret + tm * x * a[i]) % M;
    }
    return (ret + M) % M;
}
ll bell_mod(int n, int mod) {
    ll ret = vis[n];
    if (ret)
        return ret;
    if (n <= 50)
        return B[n];
    ll k = 0;
    ll P = 1;
    while (P < n) {
        P = P * mod;
        ++k;
    }
    P /= mod;
    --k;
    return vis[n] = (k * bell_mod(n - P, mod) + bell_mod(n - P + 1, mod)) % mod;
}
void f(int n, int mod) {
    cnt = 0;
    int x = mod;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            fac[cnt++] = i;
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1)
        fac[cnt++] = x;
    for (int i = 0; i < cnt; ++i) {
        bell(50, fac[i]);
        vis.clear();
        a[i] = bell_mod(n, fac[i]);
    }
    ll ans = CRT(a, fac, cnt);
    cout << ans << endl;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        f(n, MOD);
    }
    return 0;
}