#include<bits/stdc++.h>
using namespace std;
const int N=1001*1001;
int lucky[N+10],cnt=1;
bool vis[N+10];
void init(int a){
	for(int i=ceil(sqrt(a));i<=1001;i++){
		if(vis[i*i]) continue;
		for(int j=1;j*i*i<=N;j++){
			vis[j*i*i]=1;
			lucky[cnt]=j*i*i;cnt++;
		} 
	}
}
int find(int x){
	int pos=lower_bound(lucky+1,lucky+cnt,x)-lucky;
	return lucky[pos];
}
int main(){
	int a,n;
	cin>>a>>n;
	init(a);
	while(n--){
		int x;
		cin>>x;
		if(vis[x]) cout<<"lucky"<<endl;
		else cout<<find(x)<<endl;
	}
	return 0;
}