#include <bits/stdc++.h>
using namespace std;
const int MAX=1e8;
int n,a,t;
int book[MAX];
int main()
{
	cin>>a>>n;
	for(int i=1;i<1000;i++)
	{
		if(book[i]==0)
		{
			for(int j=i*i*2;j<1000;j+=i)
			{
				book[j]=1;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		cin>>t;
		if(t>=a&&(sqrt(t)*sqrt(t)==t||book[t]==1))
		{
			cout<<"lucky";
		}
		else
		{
			for(t=t+1;;t++)
			{
				if(t>=a&&(sqrt(t)*sqrt(t)==t||book[t]==1))
				{
					cout<<t;
					break;
				}
			}
		}
		cout<<endl;
	}
    return 0;
}