题目描述

希蒙认为所有大于等于a的完全平方数都是他的他所超级喜欢的。

希蒙还认为，所有超级喜欢的数的倍数都是他的喜欢的。自然地，简单点说希蒙喜欢所有a以上的完全平方数及其倍数。

给你n个数，请判断每个数是否是希蒙喜欢的。如果是则输出lucky，如果不是则输出比它大的最小的希蒙喜欢的数。

输入格式

第一行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$。