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