#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int m,q;
int tot;
pair<int,int> d[30];
void prep(){
    for(int i=2;i*i<=m;i++)
        if(m%i==0){
            tot++; d[tot].first=i;
            while(m%i==0){
                d[tot].second++;
                m/=i;
            }
        }
    if(m>1)
        d[++tot]={m,1};
}
int calc(int p,int k,int r){
    int pk=1; for(int i=0;i<k;i++) pk*=p;
    r%=pk;
    if(p==2){
        if(r==0) return pk;
        if(r==(pk>>1)) return pk;
        for(int i=0;r>>i;i++)
            if((r>>i&1)&&((r>>i+1)&1)) return 0;
        return pk*2;
    }
    if(p%4==3){
        if(r==0) return k&1?pk/p:pk;
        int c=0;
        for(;r%p==0;r/=p) c++;
        return c&1?0:pk/p*(p+1);
    }
    if(p%4==1){
        if(r==0) return pk/p*((k+1)*(p-1)+1);
        if(r%p==0) return pk/p*(p-1)*2;
        return pk/p*(p-1);
    }
}
int work(int z){
    int ans=1;
    for(int i=1;i<=tot;i++)
        ans*=calc(d[i].first,d[i].second,z);
    return ans;
}
int main(){
    scanf("%d %d",&m,&q);
    prep();
    while(q--){
        int z; scanf("%d",&z);
        printf("%d ",work(z));
    }
    puts("");
    return 0;
}