#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, N;
    cin >> a >> N;

    vector<int> query(N);
    int maxX = 0;

    // 读入所有询问，并记录询问中的最大值
    for (int i = 0; i < N; i++) {
        cin >> query[i];
        maxX = max(maxX, query[i]);
    }

    // 找到不小于 a 的最小完全平方数
    int p = sqrt(a);
    while (1LL * p * p < a) p++;

    int firstSquare = p * p;

    /*
    firstSquare 本身是超级幸运数，
    因此它的所有倍数都是幸运数。

    任意一个数向后增加不超过 firstSquare，
    一定可以遇到 firstSquare 的某个倍数。
    */
    int limit = maxX + firstSquare;

    // lucky[i] 表示 i 是否为幸运数
    vector<bool> lucky(limit + 1, false);

    /*
    枚举所有不小于 a 的完全平方数 square，
    将 square 的所有倍数标记为幸运数。
    */
    for (int i = p; 1LL * i * i <= limit; i++) {
        int square = i * i;

        for (int j = square; j <= limit; j += square)
            lucky[j] = true;
    }

    /*
    nxt[i] 表示不小于 i 的第一个幸运数。

    从右向左扫描：
    如果当前位置是幸运数，就更新最近的幸运数。
    */
    vector<int> nxt(limit + 1);
    int nearest = -1;

    for (int i = limit; i >= 1; i--) {
        if (lucky[i]) nearest = i;
        nxt[i] = nearest;
    }

    // 回答每个询问
    for (int x : query) {
        if (lucky[x]) cout << "lucky\n";
        else cout << nxt[x] << '\n';
    }

    return 0;
}