#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=30;
int n,m,k;
int p[N],t[N];
vector<int>pw[N];
ll solve(int i,int p,int k,int z,bool tag=0){
	if(!k)return 1;
	if(tag)return pw[i][k];
	return p*solve(i,p,k-1,z/p,0);
}
ll calc(int i,int p,int k,int z){
	// ll cnt=0;
	// for(int x=0;x<pw[i][k];x++){
	// 	for(int y=0;y<pw[i][k];y++){
	// 		if((1ll*x*x+1ll*y*y)%pw[i][k]==z%pw[i][k])cnt++;
	// 	}
	// }
	// return cnt;
	if(p==2){
		if(k==1)return 2;
		if(k==2){
			int cnt=0;
			for(int x=0;x<p*p;x++){
				for(int y=0;y<p*p;y++){
					if((x*x+y*y)%(p*p)!=z%(p*p))continue;
					cnt++;
				}
			}
			return cnt;
		}
		ll res[2]={-1,-1},ans=0;
		for(int x=0;x<p*p;x++){
			for(int y=0;y<p*p;y++){
				if((x*x+y*y)%(p*p*p)!=z%(p*p*p))continue;
				int t=x%2||y%2;
				// debug("solve",x,y,i,p,k-3,z/p/p/p,t,solve(i,p,k-3,z/p/p/p,t));
				if(!~res[t])res[t]=solve(i,p,k-3,z/p/p/p,t);
				ans+=res[t]*(t?1:p);
			}
		}
		return ans*p*p;
	}
	ll ans=0;
	if(p%4==3){
		if(z%p==0)ans=0;
		else ans=p+1;
	}else{
		if(z%p==0)ans=2*p-2;
		else ans=p-1;
	}
	return ans*solve(i,p,k-1,z/p,1)+(z%p==0?solve(i,p,k-1,z/p,0):0);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i*i<=n;i++){
		if(n%i)continue;
		p[++k]=i;
		for(;n%i==0;n/=i)t[k]++;
	}
	if(n>1){
		p[++k]=n,t[k]=1;
	}
	for(int i=1;i<=k;i++){
		pw[i].assign(t[i]+1,0);
		for(int j=pw[i][0]=1;j<=t[i];j++){
			pw[i][j]=pw[i][j-1]*p[i];
		}
	}
	// debug("pri",ary(p,1,k));
	// debug("cnt",ary(t,1,k));
	for(int x;m--;){
		scanf("%d",&x);
		ll ans=1;
		for(int i=1;i<=k;i++){
			// debug("calc",i,p[i],t[i],x,calc(i,p[i],t[i],x));
			ans*=calc(i,p[i],t[i],x);
		}
		printf("%lld%c",ans,"\n "[m>0]);
	}
	return 0;
}