Lucky Transformation

Given an integer a, all perfect squares greater than or equal to a are defined as the super lucky numbers. In other words, any number of the form \(n^2\) (with \(n \in \mathbb{N}\)) such that \(n^2 \ge a\) is a super lucky number. Moreover, any multiple of a super lucky number is considered a lucky number (note that every super lucky number is itself lucky).

For any given positive integer x, your task is to determine whether x is a lucky number. If x is not a lucky number, you must repeatedly add 1 until you reach a lucky number. This process is called lucky transformation. For example, if \(a=4\), then the smallest super lucky number is \(4\) (since \(2^2=4\)), and while \(1\) is not lucky, after applying the +1 operation three times, it transforms into \(4\). Hence, the lucky transformation of \(1\) is \(4\>.

More formally:

• A number \(s\) is a super lucky number if \(s = n^2\) for some positive integer \(n\) and \(s \ge a\).
• A number \(x\) is a lucky number if there exists a super lucky number \(s\) (with \(s \le x\)) that divides \(x\) (i.e. \(x \bmod s = 0\)).
• If \(x\) is not lucky, find the smallest number \(y\) (where \(y \ge x\)) such that \(y\) is lucky.

The input starts with two integers: a and N, the threshold and the number of queries respectively. The following N lines each contain one integer. For each query, if the number is lucky, output Lucky (without quotes); otherwise, output its lucky transformation (i.e. the smallest lucky number greater than or equal to the given number).

inputFormat

The first line contains two integers a and N separated by a space, where a is the threshold, and N is the number of queries.

The next N lines each contain one integer representing a query.

outputFormat

For each query, output a single line. If the number is a lucky number, output Lucky; otherwise, output the lucky transformation of the number (the smallest lucky number that is greater than or equal to it).

sample

4 3
1
4
10

4
Lucky
12