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 standard input,
• 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 to the standard output. 

Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. The first line of each test case 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 output for each test case 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 NO, if the minimal length of the K-representation of the number a_i is grater than 8. 

Example

Sample input:
1
5
2
12
31168

Sample output
4
NO