MONODIG - Monodigital Representations

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 a1,...,an, 1<=ai<=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 ai, 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 ai is grater than 8. 

Example

Sample input:
1
5
2
12
31168

Sample output
4
NO

Added by:Piotr Łowiec
Date:2004-09-13
Time limit:1.647s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:6th Polish Olympiad in Informatics, stage 1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.