Let K be a decimal digit different from 0. We say that an arithmetic expression is a K-representation of the integer X if a value of this expression is X and if it contains only numbers composed of a digit K. (All the numbers are of course decimal). The following arithmetical operations are allowed in the expression: addition, subtraction, multiplication and division. Round brackets are allowed too. Division may appear only when a dividend is a multiple of a divisor.

Example

Each of the following expressions is the 5-representation of the number 12:

• 5+5+(5:5)+(5:5)
• (5+(5))+5:5+5:5
• 55:5+5:5
• (55+5):5

The length of the K-representation is the number of occurrences of digit K in the expression. In the example above the first two representations have the length 6, the third - 5, and the forth - 4.

Task

Write a program which: 

• reads the digit K and the series of numbers from the text file MON.IN,
• verifies for each number from the series, whether it has a K-representation of length at most 8, and if it does, then the program finds the minimal length of this representation,
• writes results in the output file MON.OUT. 

Input

The first line of the input file MON.IN contains digit K, K is en element of {1,...,9}. The second line contains number n, 1<=n<=10. In the following n lines there is the series of natural numbers a₁,...,a_n, 1<=a_i<=32000 (for i=1,..,n), one number in each line. 

Output

The file MON.OUT composes of n lines. The i-th line should contain: 

• exactly one number which is the minimal length of K-representation of a_i, assuming that such a representation of length not grater then 8 exists,
• one word NIE (means 'no' in Polish), if the minimal length of the K-representation of the number a_i is grater than 8. 

Example

For the input file MON.IN: 

5
2
12
31168

the correct answer is the text file MON.OUT:

4
NIE

Your program should look for the file MON.IN in the current directory and produce the output file MON.OUT in current directory too. The file containing source code of your program should have a name MON.???, whereas you should put three-letter abbreviation of used programming language name instead of ???. The same program in executable form should be written in file MON.EXE