Catalin_si_armata

//Dobricean Iount
#include <fstream>
char IN[]="armata.in",OUT[]="armata.out";
std::fstream cin(IN,std::ios::in),cout(OUT,std::ios::out);

bool erat[5000000];
int x,cnt,k,n;

void ertaostene()
{std::ios::sync_with_stdio(false);
   long long i,j;
erat[1]=1;
   long long  DIM=4*n+100;
    for(i=2 ; i<DIM/2; i++)
        if(erat[i]==false)
            for(j=i*2; j<DIM; j=j+i)
                erat[j]=true;

}

void det(int l)
{

if(erat[l*3-1]==true && l*3-1<=n)
 {cnt++;
 }
else
if(l*3-1<=n)
    det(l*3-1);
if(erat[l*3]==true && l*3<=n)
 {cnt++;
 }
else
if(l*3<=n)
    det(l*3);
    if(erat[l*3+1]==true && l*3+1<=n)
 {cnt++;
 }
else
if(l*3+1<=n)
    det(l*3+1);

}

int main()
{ int i;
cin>>n>>x;
ertaostene();
while(x>0)
{ cin>>i;
if(erat[i]==false) {cout<<-1<<"\n";
}
else
    cnt=0,det(i),cout<<cnt<<"\n";
x--;
}

}