#include<iostream>
#define cl cout << l << endl;
using namespace std;
int n, k;
string l = "lucky";
bool allnum[10001000];
void init() {
	for (int i = 2, x; i * i <= 10000000; i++) {
		x = i * i;
		for (int i = 1; i * x <= 10000000; i++)
			allnum[i * x] = true;
	}
}
int main() {
	init();
	cin >> k >> n;
	for (int i = 1; i <= n; i++) {
		int now;
		cin >> now;
		if (now < k) {
			if(allnum[k])
				cout << k << endl;
			else {
			    int now1 = k;
				while (allnum[now1] == 0) 
					now1++;
				cout << now1 << endl;
			}
		} else if (now == k) {
			cl
		} else {
			if (allnum[now])
				cl
			else {
				while (allnum[now]==0)
					now++;
				cout << now << endl;
			}
		}

	}
	return 0;
}