J :: Countdown

Time Limit: 15 Seconds    Memory Limit: 32768 KB
Special Judge

The "Countdown" TV show has a part that consists of obtaining a number by combining six different numbers using the basic mathematical operations: addition, subtraction, product and division. The basic rules for the game are:

• The contestant selects six of twenty-four shuffled tiles. The tiles are arranged into two groups: four "large numbers" (25, 50, 75 and 100) and the remainder "small numbers", which comprise two each of the numbers 1 to 10. Hence the tiles have the values {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100}.
• The contestant chooses how many large numbers are in the selection; anywhere from none.
• The contestants then have thirty seconds to get a number as close to the target as possible by combining the six selected numbers using addition, subtraction, multiplication and division.
• Not all numbers need to be used.
• A number can be used as many times as it appears.
• Fractions are not allowed, only positive integers may be used at any stage of the calculation.

Example:
• Contestant requests two large numbers and four small numbers.
• Selection is: 75 50 2 3 8 7
• Randomly generated target is: 812
• Contestant declares result: 813
• Contestant gives details: 75 + 50 = 125; 125 - 8 = 117; 117 × 7 = 819; 3 × 2 = 6; 819 - 6 = 813
• Expert notes: 50 + 8 = 58; 7 × 2 = 14; 14 × 58 = 812

Your task is to write a program that calculates the best sequence of operations that lead to the target number T. If there is no way to get T, give the closest solution.

Input

The input consists of several cases, one per line. The ?rst line indicates the number of cases C to process (1 ≤ C ≤ 50). Each of the following C lines contains six natural numbers from the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100} and another natural number T (1 ≤ T ≤ 999) that indicates the target.

Output

The output for each case will be a set of lines with the following format:

• First line: Target: number T
• n lines: sequence of operations, the format is <operand2> <operator> <operand2> = <result>
• Last line: Best approx: number obtained
• Blank line

See example for a better understanding. If there is more than one best approximation, all of them will be considered valid. The sequence of operations should be valid, you should never use a value before you obtain it. It is OK to print more operations than needed as long as they are valid. Note that all the numbers and operators must be separated by at least one space.

Sample Input

3
1 75 100 5 3 25 25
100 100 100 100 100 75 345
1 3 1 10 100 75 345

Sample Output

Target: 25
Best approx: 25

Target: 345
100 + 100 = 200
75 + 100 = 175
200 * 175 = 35000
35000 - 100 = 34900
34900 / 100 = 349
Best approx: 349

Target: 345
100 - 10 = 90
3 * 90 = 270
270 + 75 = 345
Best approx: 345
Submit

Source: SWERC 2012