#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
ll Spow(ll x,ll y){
	ll ans=1;
	for(int i=1;i<=y;i++)
		ans*=x;
	return ans;
}
const int N=2e5+10;
int mod,q;
ll exgcd(ll x,ll y,ll &a,ll &b){
	if(!y)return a=1,b=0,a;
	ll px,py,d;
	d=exgcd(y,x%y,px,py);
	a=py,b=px-x/y*py;
	return d;
}
ll inv(ll x,ll mod){
	ll A,B;
	exgcd(x,mod,A,B);
	return (A%mod+mod)%mod;
}
void solve(){
	//don't forget to open long long
	std::cin>>mod>>q;
	ve<std::pair<int,int>>P;int R=mod;
	for(int i=2;i*i<=R;i++)
		if(R%i==0){
			P.pd({i,0});
			while(R%i==0)
				P.back().second++,R/=i;
		}
	int z;
	if(R!=1)P.pd({R,1});
	auto solve1=[&](ll p,ll k)->ll{
		auto getcorner=[&](ll z)->ll{
			ll dz=z%p;
			if(dz)return p-(((p-1)/2)%2?-1:1);
			else return p+(p-1)*(((p-1)/2)%2?-1:1)-1;
		};
		ve<ll>G(k+2),F(k+2);
		auto get=[&](ll k,ll z,auto self)->ll{
			if(k==1)return getcorner(z);
			return self(k-1,z,self)*p;
		};
		auto dfs=[&](ll k,ll z,auto self)->ll{
			if(!k)return 1;
			if(k==1)return get(k,z,get)+(z%p==0);
			ll ans=get(k,z,get);
			if(z%(p*p)==0)
				ans+=self(k-2,z/(p*p),self)*p*p;
			return ans;
		};
		return dfs(k,z,dfs);
	};
	auto solve2=[&](ll k)->ll{
		k--;
		ve<ll>F(k+5),G(k+5);
		for(int P=0;P<=2;P++){
			ll p=Spow(2,P+1);
			for(int i=0;i<p;i++)
				for(int j=0;j<p;j++)
					if((Spow(i,2)+Spow(j,2))%p==z%p)
						if((i&1)||(j&1))
							G[P]++;
		}
		for(int i=3;i<=k;i++)G[i]=G[i-1]<<1;
		auto dfs=[&](ll k,ll z,auto self)->ll{
			if(k<=2){
				ll p=Spow(2,k+1);
				for(int i=0;i<p;i++)
					for(int j=0;j<p;j++)
						if((Spow(i,2)+Spow(j,2))%p==z%p)
							F[k]++;
				return F[k];
			}
			F[k]+=G[k];
			if(z%4==0)
				F[k]+=self(k-2,z/4,self)<<2;
			return F[k];
		};
		return dfs(k,z,dfs);
	};
	ll S=1;
	while(q--){
		std::cin>>z;
		for(auto &p:P){
			if(p.first==2)
				S*=solve2(p.second);
			else S*=solve1(p.first,p.second);
		}
		std::cout<<S<<' ';S=1;
	}
	std::cout<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T=1;
	//std::cin>>T;
	while(T--)solve();

	return 0;
}