#include<bits/stdc++.h>
using namespace std;
int a,n;
bool lucky[2000010]={0};
vector<int>luck;
void shai(int x){for(int i=x;i<=2000010;i+=x){
lucky[i]=1;luck.push_back(i);}}
bool ch(int x){
	int k=sqrt(x);
	return k*k==x;
}
int main(){
	cin>>a>>n;
	for(int i=a;i<=2000010;i++)if(ch(i))shai(i);
	sort(luck.begin(),luck.end());
	while(n--){
		int x;
		cin>>x;
		if(lucky[x])cout<<"lucky"<<endl;
		else{
			auto it=upper_bound(luck.begin(),luck.end(),x);
			cout<<*it<<endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int M = 1000002;
bool sq[M] = {0};
bool luck[M] = {0};
int nxt[M] = {0};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a, n;
    cin >> a >> n;
    for(int i=1; i*i<M; i++) {
        if(i*i >= a) sq[i*i] = true;
    }
    for(int i=a; i<M; i++) {
        if(sq[i]) {
            for(int j=i; j<M; j+=i) {
                luck[j] = true;
            }
        }
    }
    int last = M;
    for(int i=M-1; i>=1; i--) {
        if(luck[i]) last = i;
        nxt[i] = last;
    }
    while(n--) {
        int x;
        cin >> x;
        if(luck[x]) cout << "lucky\n";
        else cout << nxt[x] << "\n";
    } 
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

const int MAX_N = 1000000; // 最大数据范围

bool is_lucky[MAX_N + 2];   // 标记幸运数
int next_lucky[MAX_N + 2];  // 存储每个数对应的最小幸运数

int main() {
    int a, T;
    scanf("%d%d", &a, &T);

    // 初始化：全部非幸运数
    for (int i = 1; i <= MAX_N; ++i) {
        is_lucky[i] = false;
    }

    // 筛法标记幸运数
    for (int i = 1; i * i <= MAX_N; ++i) {
        int s = i * i;
        if (s >= a && s <= MAX_N) {
            for (int j = s; j <= MAX_N; j += s) {
                is_lucky[j] = true;
            }
        }
    }

    // 预处理后缀数组：next_lucky[i] = ≥i的最小幸运数
    next_lucky[MAX_N + 1] = 0; // 哨兵值
    for (int i = MAX_N; i >= 1; --i) {
        if (is_lucky[i]) {
            next_lucky[i] = i;
        } else {
            next_lucky[i] = next_lucky[i + 1];
        }
    }

    // 处理每个查询
    while (T--) {
        int x;
        scanf("%d", &x);
        if (is_lucky[x]) {
            printf("lucky\n");
        } else {
            printf("%d\n", next_lucky[x]);
        }
    }

    return 0;
}

#include <cmath>
using namespace std;
const int MAX = 1000001; // 根据数据规模设定
bool is_lucky[MAX];
int next_lucky[MAX];

int main() {
    int a, N, x;
    scanf("%d%d", &a, &N);
    
    // 标记完全平方数及其倍数
    for (int i = 1; i < MAX; i++) {
        int root = sqrt(i);
        if (i >= a && root * root == i) is_lucky[i] = true;
    }
    for (int i = 1; i < MAX; i++) {
        if (!is_lucky[i]) continue;
        for (int j = i * 2; j < MAX; j += i) 
            is_lucky[j] = true;
    }
    
    // 计算最近幸运数
    next_lucky[MAX - 1] = is_lucky[MAX - 1] ? MAX - 1 : -1;
    for (int i = MAX - 2; i >= 1; i--) {
        next_lucky[i] = is_lucky[i] ? i : next_lucky[i + 1];
    }
    
    // 处理查询
    while (N--) {
        scanf("%d", &x);
        if (is_lucky[x]) printf("lucky\n");
        else printf("%d\n", next_lucky[x]);
    }
    return 0;
}