#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vl = vector<ll>;
const int M = 1000000009;

int prod(int a, int b, int m) {
	return ll(a) * b % m;
}
int binpow(int a, int b, int m) {
	int ans = 1;
	while (b) {
		if (b & 1)
			ans = prod(ans, a, m);
		a = prod(a, a, m);
		b >>= 1;
	}
	return ans;
}
ll intpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)
			ans *= a;
		a *= a;
		b >>= 1;
	}
	return ans;
}
int dif(int a, int b, int m) {
	if ((a -= b) < 0) a += m;
	return a;
}
int sum(int a, int b, int m) {
	if ((a += b) >= m) a -= m;
	return a;
}
int inv(int a, int m) {
	return binpow(a, m - 2, m);
}
vpii factor(int n) {
	vpii ans;
	for (int i = 2; i * i <= n; ++i)
		if (n % i == 0) {
			ans.emplace_back(i, 1); n /= i;
			while (n % i == 0) {
				++ans.back().second;
				n /= i;
			}
		}
	if (n >= 2) ans.emplace_back(n, 1);
	return ans;
}
int rev(int a, int m) {
	if (a == 1) return 1;
	return (1 - ll(rev(m % a, a)) * m) / a + m;
}
int crt(const int x, const int y, const int mx, const int my) {
	int m = mx * my;
	return sum(prod(prod(x, my, m), rev(my % mx, mx), m), prod(prod(y, mx, m), rev(mx % my, my), m), m);
}
int legendre(int a, int p) {
	return binpow(a, (p - 1) / 2, p);
}
ll fqa(const int pa, const pii& f, const int z) {
	const int p = f.first;
	const int t = f.second;
	int k = 0;
	int resa = z;
	if (resa == 0) k = t;
	else
		while (resa % p == 0) {
			resa /= p;
			++k;
		}
	resa %= p;

	if (p == 2) {
		if (t == 1) {
			if (z == 0) return 1;
			if (z == 1) return 2;
		}
		else if (t == 2) {
			if (z == 0) return 0;
			if (z == 1) return 8;
			if (z == 2) return 4;
			if (z == 3) return 0;
		}
		int arrans[] = { 0,4,4,0,0,8,0,0 };
		int y = z % 8;
		return arrans[z] * intpow(2, t - 1);
	}
	else if (p % 4 == 3) {
		if (k >= 1) return 0;
		if (legendre(z, p) == 1) return (p + 1) * intpow(p, t - 1);
		return (p + 1) * intpow(p, t - 1);
	}
	else {
		if (k >= 1) return (p - 1) / 2 * intpow(p, t - 1);
		if (legendre(z, p) == 1) return (p - 1) * intpow(p, t - 1);
		return (p - 1) * intpow(p, t - 1);
	}
}
ll find_ans(const int pa, const pii& f, const int z) {
	const int p = f.first;
	const int t = f.second;
	int k = 0;
	int resa = z;
	if (resa == 0) k = t;
	else
		while (resa % p == 0) {
			resa /= p;
			++k;
		}
	resa %= p;
	ll ans = 0;
	for (int i = 0; i <= t; ++i) {
		ll curans = 0;
		int g = min(t, 2 * i);
		if (k < g) continue;
		int pg = intpow(p, g);
		if (g == t) {
			curans = intpow(p, 2 * (t - i));
			if (i < t) curans -= intpow(p, 2 * (t - i - 1));
		} else {
			ll pw = intpow(p, g);
			curans = pw * fqa(pa / pg, { p, t - g }, (z / pg) % (pa / pg));
		}
		ans += curans;
	}
	return ans;
}
ll find_ans(const vi& pa, const vpii& f, const int z) {
	ll ans = 1;
	const int F = f.size();
	for (int i = 0; i < F; ++i)
		ans *= find_ans(pa[i], f[i], z % pa[i]);
	return ans;
}

vl find_ans(int m, const vi& z) {
	vpii f = factor(m);
	const int F = f.size();
	const int n = z.size();
	vi pa(F);
	for (int i = 0; i < F; ++i)
		pa[i] = intpow(f[i].first, f[i].second);
	vl ans(n);
	for (int i = 0; i < n; ++i)
		ans[i] = find_ans(pa, f, z[i]);
	return ans;
}
bool solve_test() {
	int m, n;
	if (!(cin >> m >> n)) return false;
	vi z(n);
	for (int i = 0; i < n; ++i)
		cin >> z[i];
	vl ans = find_ans(m, z);
	for (int i = 0; i < n; ++i)
		cout << ans[i] << " \n"[i == n - 1];
	return true;
}
void solve_tests() {
	while (solve_test());
}
int main() {
#ifdef ONPC
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve_tests();
}