#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a,x;
bool vis[1000005];
int main(){
	cin>>a>>n;
	for(int i=a;i<=1000005;i++){
		if(vis[i]) continue;
		double sq=sqrt(i*1.0);
		if(sq-int(sq)==0){
			for(int j=1;j*i<=1000005;j++){
			    vis[i*j]=1;
		    }
		}	
	}
	while(n--){
		cin>>x;
		if(vis[x]) cout<<"lucky\n";
		else{
			for(int i=max(x,a);i<=100002;i++){
				if(vis[i]){
					cout<<i<<'\n';
					break;
				}
			}
		}
		
	}
}