#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<tuple<int , int , int> , ll>mp;
ll G(int p , int k , int z)
{
	if(p == 2 && k <= 2)
	{
		int v = k == 1 ? 2 : 4 , ans = 0;
		for(int x = 0 ; x < v ; x++)
			for(int y = 0 ; y < v ; y++)
				if(x != 2 || y != 2)
					ans += (x * x + y * y) % v == z % v;
		return ans;
	}
	if(k <= 1)
	{
		int r = p % 4;
		if(!z)return r == 1 ? 2 * p - 1 : 1;
		else return r == 1 ? p - 1 : p + 1;
	}
	if(mp.find({p , k , z}) != mp.end())
		return mp[{p , k , z}];
	return mp[{p , k , z}] = p * G(p , k - 1 , z);
}
ll F(int p , int k , int z)
{
	if(p == 2 && k <= 2)
	{
		int v = k == 1 ? 2 : 4 , ans = 0;
		for(int x = 0 ; x < v ; x++)
			for(int y = 0 ; y < v ; y++)
				ans += (x * x + y * y) % v == z % v;
		return ans;
	}
	if(k <= 1)
	{
		int r = p % 4;
		if(!z)return r == 1 ? 2 * p - 1 : 1;
		else return r == 1 ? p - 1 : p + 1;
	}
	ll res = G(p , k , z) , p2 = (ll)p * p;
	if(z % p2 == 0)res += p2 * F(p , k - 2 , z / p2);
	return res;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	int m , q , t; vector<pair<int , int> >fac;
	cin >> m >> q; t = m;
	for(int i = 2 ; (ll)i * i <= t ; i++)
	{
		if(t % i == 0)
		{
			int k = 0;
			while(t % i == 0)t /= i , k++;
			fac.push_back({i , k});
		}
	}
	if(t > 1)fac.push_back({t , 1});
	while(q--)
	{
		int z; ll res = 1; cin >> z;
		for(auto [p , k] : fac)res = res * F(p , k , z);
		cout << res << " ";
	}
	cout << "\n";
	return 0;
}