题目描述

小杨认为，所有大于等于a的完全平方数都是他的超级幸运数。

小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数，小杨规定，可以将它一直 +1，直到它变成一一个幸运数。我们把这个过程叫做幸运化。例如，如果a=4,那么4是最小的幸运数，而1不是，但我们可以连续对1做3次+1操作，使其变为4,所以我们可以说，1幸运化后的结果是4。

现在，小样给出N个数，请你首先判断它们是不是幸运数;接着,对于非幸运数,请你将它们幸运化。

输入格式

第一行2个正整数a, N。

接下来N行，每行一个正整数x，表示需要判断(幸运化)的数。

输出格式

样例 #1

样例输入 #1

2 4
1
4
5
9

样例输出 #1

4
lucky
8
lucky

数据规模

对于30%的测试点，保证$a,x≤100, N≤100$。

对于60%的测试点，保证 $a,x≤10^6$。

对于所有测试点，保证 $a≤1000001$ ;保证 $N ≤ 2 \times 10^5$;保证 $1 \leq x \leq 1000001$。