#include <iostream>
//#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#define ll long long

using namespace std;
ll big = 95041567;  // 2333054710
ll b[10005] = { 0 };
ll c[10005][10005];
int main(void) {
    int t;
    ll n;
    cin >> t;
    b[0] = b[1] = 1;
    c[0][0] = 0;
    c[1][0] = c[1][1] = 1;
    for (int i = 2; i <= 10000; ++i) {
        for (int j = 0; j <= i - 1; ++j) {
            if (j > 0 && j < i - 1)
                c[i - 1][j] = (c[i - 2][j] + c[i - 2][j - 1]) % big;
            else
                c[i - 1][j] = 1;
            b[i] += (b[j] * c[i - 1][j]) % big;
        }
    }
    for (int i = 0; i < t; ++i) {
        cin >> n;
        if (n <= 10000) {
            cout << b[n] % big << endl;
        } else {
        }
    }
    return 0;
}