#include<bits/stdc++.h>
using std::cin;
using std::cout;
using u64 = unsigned long long;
using ll = long long;
int a[1 << 20];
int pow(int a, int b, int mod) {
	int ans = 1;
	for(;b;b >>= 1, a = (u64) a * a % mod) if(b & 1)
		ans = (u64) ans * a % mod;
	return ans;
}
int chkp(int p) {
	return pow(p - 1, p / 2, p);
}
std::vector<int> table(int m) {
	std::vector<int> res(m);
	for(int i = 0;i < m;++i)
	for(int j = 0;j < m;++j)
		++ res[(i * i + j * j) % m];
	return res;
}
ll calc2(int c, int pos) {
	if(c == 1) return 2;
	if(pos == 0) return 1 << c;
	if(pos == 1) return 2 << c;

	int d = c - 1;
	for(;1 << d > pos;) -- d;
	if(pos == 1 << d) {
		if(d == c - 1) return 1 << c;
		return 2 << c;
	}
	if(pos == 3 << (d - 1)) return 0;
	return calc2(c, pos - (1 << d));
}
ll calc(int p, int c, int pos) {
	ll base = 0;
	int state = 0;
	if(chkp(p) == 1) {
		base = p - 1;
		state = 1;
	} else {
		base = p + 1;
	}
	for(int i = 1;i < c;++i) {
		base *= p;
	}
	if(pos) {
		int cnt = 1;
		for(;pos % p == 0;) {
			pos /= p;
			cnt += 1;
		}
		if(!state) {
			return cnt % 2 * base;
		}
		return cnt * base;
	} else {
		std::vector<int> cnt(c + 1);
		cnt[c] = 1;
		for(int i = c - 1;i >= 0;--i) {
			cnt[i] = cnt[i + 1] * p;
		}
		for(int i = 0;i < c;++i) {
			cnt[i] -= cnt[i + 1];
		}
		ll all = 1;
		for(int i = 0;i < c;++i) {
			all *= p;
			all *= p;
		}
		for(int i = 0;i < c;++i) {
			if(state) {
				all -= (ll) cnt[i] * (i + 1) * base;
			} else {
				all -= (ll) (i + 1) % 2 * cnt[i] * base;
			}
		}
		return all;
	}
}
void debug() {
	int m = 0;
	for(int m = 0;m <= 13;++m) {
	auto res = table(1 << m);

	for(int i = 0;i < 1 << m;++i) {
		assert(res[i] == calc2(m, i));
	}
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	//debug();
	//return 0;
	int t;
	int m, n;
	// std::mt19937 gen(time(0) + (size_t) new char);
	// m = gen() % 1000 + 1;
	cin >> m >> n;
	ll ans = 1;

	int c_2 = 0;

	std::vector<std::array<int, 3>> ps;
	// auto tb = table(m);

	for(int i = 2;i * i <= m || i <= 2;++i) {
		if(m % i == 0) {
			int c = 0;
			int mul = 1;
			while(m % i == 0) {
				m /= i;
				mul *= i;
				++ c;
			}
			if(i == 2) {
				c_2 = c;
				// ans *= calc2(c, n % mul);
			} else {
				ps.push_back({i, c, mul});
				// ans *= calc(i, c, n % mul);
			}
		}
	}
	if(m > 1) {
		ps.push_back({m, 1, m});
	}
	for(int i = 0;i < n;++i) {
		int z;
		cin >> z;
		ll ans = calc2(c_2, z % (1 << c_2));
		for(auto a : ps) {
			ans *= calc(a[0], a[1], z % a[2]);
		}
		// assert(ans == tb[z]);
		cout << ans << ' ';
	}
}