#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{
			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);
		};
		ve<ll>F(k+1),G(k+1);
		F[0]=1;
		F[1]=G[1]=getcorner();
		if(!(z%p))G[1]--;
		for(int i=2;i<=k;i++)
			G[i]=G[i-1]*p,F[i]=G[i]+(z%(p*p)==0)*p*p*F[i-2];
		return F[k];
	};
	auto solve2=[&](ll k)->ll{
		ve<ll>F(k+2),G(k+2);
		for(int P=1;P<=2;P++){
			int p=Spow(2,P);
			for(int A=0;A<p;A++)
				for(int B=0;B<p;B++)
					if((Spow(A,2)+Spow(B,2))%p==z%p){
						F[P]++;
						if((A&1)&&(B&1))
							G[P]++;
					}
						
		}
		if(k<=2)return F[k];
		for(int i=3;i<=k;i++){
			G[i]=G[i-1]<<1;
			F[i]=G[i];
			if(z%4==0)
				F[i]+=4*F[i-2];
		}
		return F[k];
	};
	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;
}