题目描述

小王认为大于等于 $a$ 的完全平方数是超级幸运数，超级幸运数的倍数是幸运数。对于非幸运数，可通过不断加 $1$ 直到变为幸运数（此过程叫幸运化）。现在小王给出 $N$ 个数，需先判断是否为幸运数，对于非幸运数要进行幸运化。

输入

第一行包含 2 个正整数 $a, N$。接下来 $N$ 行，每行一个正整数 $x$ ，表示需要判断（幸运化）的数。其中，对于 $30\%$ 的测试点，$a,x \le 100,N \le 100$；对于 $60\%$ 的测试点，$a,x \le 10^6$；对于所有测试点，$a \le 1,000,000$，$N \le 2 \times 10^5$，$1 \le x \le 1,000,001$。

输出

输出 $N$ 行，对于每个给定的 $x$ ，若是幸运数，输出 lucky，否则输出将其幸运化后的结果。

样例

样例输入1

2 4 
1 
4 
5 
9

样例输出1

4 
lucky 
8 
lucky

样例输入2

16 11 
1 
2 
4 
8 
16 
32 
64 
128 
256 
512
1024

样例输出2

16 
16 
16 
16 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky