#include<bits/stdc++.h>
using namespace std;
int n,m; 
bool fang(int x){
	for(int i=2;i<=1000;i++){
		if((x==i*i&&x>=n)||(x>=n&&x%(i*i)==0)){
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>n>>m;
	int x;
	for(int i=0;i<m;i++){
		cin>>x;
		if(fang(x)){
			cout<<"lucky"<<endl;
		}else{
			if(x<n){
				for(int i=x+1;i<=1000000;i++){
					if(fang(i)&&i>=n){
						cout<<i<<endl;
						break;
					}
				}
			}else if(x>=n){
				for(int i=x+1;i<=1000000;i++){
					if(fang(i)){
						cout<<i<<endl;
						break;
					}
				}
			}
		}
	}
	return 0;
}