#include <bits/stdc++.h>
using namespace std;
int a,n,x;
bool m[11451451];
int main() {
	cin>>a>>n;
	for(int i=0; i*i<=2000010; i++) {
		if(m[i*i]==0 && i*i>=a) {
			for(int j=1; i*i*j<=2000010; j++) {
				m[i*i*j]=1;
			}
		}
	}
	for(int i=0; i<n; i++) {
		cin>>x;
		if(m[x]==1)cout<<"lucky"<<endl;
		else {
			for(int j=x; j<=2000010; j++) {
				if(m[j]==1) {
					cout<<j<<endl;
					break;
				}
			}
		}
	}
	return 0;
}

AC记录