C++ :

#include <bits/stdc++.h>
#define ll long long
#define uint unsigned
#define ull unsigned ll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define PB push_back
#define fi first
#define se second
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
#define CLR(a, v) memset(a, v, sizeof(a))
#define CPY(a, b) memcpy(a, b, sizeof(a))
using namespace std;
const int N = 23335;
int f[N], v[N], T, mo;
int power(int x, int y) {
    int s = 1;
    for (; y; y /= 2, x = 1ll * x * x % mo)
        if (y & 1)
            s = 1ll * s * x % mo;
    return s;
}
int main() {
    scanf("%d%d", &T, &mo);
    For(i, 0, N - 1) f[i] = 1;
    v[1] = 1;
    For(i, 2, N - 1) {
        int v1 = f[i];
        ull v2 = 1ll * f[1] * v[i - 1] % mo;
        For(j, 1, i - 2) {
            v2 += 2ll * f[i - j] * v[j];
            if (!(j & 7))
                v2 %= mo;
        }
        v2 %= mo;
        f[i] = 1ll * (v1 + v2) * power(i, mo - 2) % mo;
        v[i] = (1ll * i * f[i] + v1) % mo;
        For(j, 2, (N - 1) / i) f[i * j] = (f[i * j] + 1ll * f[i] * i) % mo;
    }
    while (T--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", x <= 1 ? f[x] : 2 * f[x] % mo);
    }
}