Monodigital Expression

The digit K is one of the digits from 1 to 9. An expression for a positive integer X that uses several copies of the digit K and only the four arithmetic operations +, -, *, and / is called a K-expression of X.

Parentheses may be used in expressions. Division uses only the integer quotient. You may also concatenate several copies of K into one number. For example, when K = 5, the numbers 5, 55, and 555 may be used.

The length of a K-expression is the number of copies of K used in it. Given K, find the shortest possible K-expression length for each requested positive integer.

The first line contains the digit K.

The second line contains the number n of positive integers whose shortest expression lengths must be found. 1 <= n <= 1,000.

Each of the next n lines contains one positive integer a. For every a, 1 <= a <= 32,000.

For each input integer, output the minimum length of a possible K-expression, one per line, in input order.

If the minimum length is greater than 8, or if the integer cannot be expressed with length at most 8, output NO.