#include <bits/stdc++.h>

const int N = 23334;
int n, T, mod, f[N], g[N], sum[N];

int fastpow(int x, int p) {
	int r = 1;
	while (p) {
		if (p & 1) r = 1ll * r * x % mod;
		x = 1ll * x * x % mod;
		p >>= 1;
	}
	return r;
}

void solve() {
	int inv2 = (mod + 1) >> 1;
	for (int n = 1; n < N; ++n) {
		if (n == 1) {
			f[n] = g[n] = 1;
		}
		else {
			__int128 total = 0;
			for (int i = 1; i < n; ++i)
				total += 1ll * f[i] * sum[n - i];
			f[n] = 2ll * (f[n] + total % mod) * fastpow(n, mod - 2) % mod;
			g[n] = 1ll * inv2 * f[n];
		}
		for (int i = n; i < N; i += n) {
			sum[i] = (sum[i] + 1ll * n * g[n]) % mod;
			if (i > n) {
				f[i] = (f[i] + 1ll * n * g[n]) % mod;
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> T >> mod;
	solve();
	for (int i = 1; i <= T; ++i) {
		int n;
		std::cin >> n;
		std::cout << f[n] << '\n';
	}
	return 0;
}