Change

INPUT FILE: change.in
OUTPUT FILE: change.out

Given a set S of denominations and an amount N try to express N only by using the elements from S.

You are subject to the following constraints:
1 - You must minimize the number of coins used
2 - No denomination can be used more than 3 times!

INPUT
The first line contains the number of test cases.
Each test case is comprised of, on separate lines:

• X, the number of elements in S; X <= 100
• S, the set of denominations, all on one line; each element of S is between 1 and 255
• Z, the number of amounts for which your program has to make change
• On each of the next Z lines, an amount N for which your program has to make change.

OUTPUT
For each denomination in each of the input sets, output the denomination N for which your program has to make change, followed by the required set of coins (denomination and number of times used) OR �No solution� if no solution exists.

Separate each test case by a blank line.

Sample Input File

2
5
2 3 4 5 6
4
1
4
7
8
2
2 4
2
3 20

Output for Sample Input

N = 1: No solution
N = 4: $4 x 1
N = 7: $3 x 1, $4 x 1     [OR: $2 x 1, $5 x 1, either is okay]
N = 8: $4 x 2

N = 3: No solution
N = 20: No solution