Digits4All

Peter has some digits $d_{1},\ldots,d_{D}$, each of them is available in infinite amount. Using the digits and addition, multiplication and concatenation he wants to represent positive numbers. For example if his digits are 1, 2, 5 and the number to be represented is 16, then some of its legal representations are:

16 =  5+5+5+1                       (by addition)
16 =  4*4 = (2+2)*(2+1+1)           (by addition, by multiplication)
16 =  (1)(1+5)                      (by addition, concatenation)

If the number to be represented is 101, then we have the following possibilities:

101 = (10)(1) = (2*5)(1)            (by multiplication, by concatenation)
101 = (10)(1) = (5+5)(1)            (by addition, by concatenation)

He does not have 0 digits, and he forbids numbers with leading zeroes, that is the representation 101=(1)(01) is not legal.

For the representation of a number $q>0$ he can use the addition, multiplication and concatenation in any combinations, but he wants to use the minimal number of digits ($m_q$) for the representation. Help him by computing these $m_q$’s!

Input specification

In the first line the $D$ is the number of different digits Peter has. In the second line comes the space separated list of his digits $d_1,\ldots,d_{D}$. In the third comes the $Q$: the number of queries that follows. Each of the next $Q$ lines has a single positive number $q_i$, the representable number.

Output specification

$Q$ lines with the number $m_{q_i}$ or with $-1$ if it is impossible to represent $q_i$ with the given digits.

Constraints

$1\le D \le 9$
$1\le d_{i} \le 9$
$1\le Q \le 1000$
$1\le q_{i} \le 20000$

Sample input 1

1. 3
2. 1 2 5
3. 2
4. 16
5. 101

download as text file

Sample output 1

1. 3
2. 3

download as text file

Sample input 2

1. 1
2. 1
3. 3
4. 2
5. 12
6. 1111

download as text file

Sample output 2

1. 2
2. 3
3. 4

download as text file

Sample input 3

1. 3
2. 2 4 6
3. 5
4. 10
5. 20
6. 30
7. 40
8. 50

download as text file

Sample output 3

1. 2
2. 3
3. 3
4. 3
5. 3

download as text file

Sample input 4

1. 4
2. 2 5 7 8
3. 7
4. 9190
5. 3644
6. 1111
7. 4846
8. 4544
9. 404
10. 4333

download as text file

Sample output 4

1. 6
2. 5
3. 5
4. 6
5. 4
6. 4
7. 6

download as text file

Sample input 5

1. 2
2. 2 3
3. 1
4. 1

download as text file

Sample output 5

1. -1

download as text file