#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
ll pow(int a,int b){ll r=1;while(b--)r=r*a;return r;}
ll g(int p,int k,int z){
	if(k==0) return 0;
	if(k==1){
		if(z) return p-(p%4==1?1:-1);
		else return (p%4==1?2*p-2:0);
	}if(p==2&&k<=3){
		int ans=0;
		for(int i=1;i<(1<<k);i++) for(int j=1;j<(1<<k);j++)
			if(((i&1)||(j&1))&&(i*i+j*j)%(1<<k)==z) ans++;
		return ans;
	}return g(p,k-1,z%pow(p,k-1))*p;
}
ll f(int p,int k,int z){
	if(k==0) return 1;
	else if(p==2&&k<=3){
		int ans=0;
		for(ll i=0;i<(1<<k);i++) for(ll j=0;j<(1<<k);j++)
			if((i*i+j*j)%(1<<k)==z) ans++;
		return ans;
	}else if(k==1){
		if(z) return p-(p%4==1?1:-1);
		else return (p%4==1?2*p-1:1);
	}else return g(p,k,z)+p*p*(z%(p*p)==0?f(p,k-2,z/p/p):0);
}// solve the equivment x^2+y^2==z (mod p^k)
int main(){
	ios::sync_with_stdio(false);
	map<int,int> mp;
	int m,_;
	cin>>m>>_;
	for(int i=2;i*i<=m;i++) if(m%i==0){
		while(m%i==0) mp[i]++,m/=i;
	}
	if(m>1) mp[m]++;
	while(_--){
		ll x,ans=1;cin>>x;
		for(auto p:mp) ans*=f(p.first,p.second,x%pow(p.first,p.second)); 
		cout<<ans<<' ';
	}
	return 0;
}