Parencedence!

Parencedence is a two-player game. A computer produces an arithmetic expression made of integer values and the binary operators +, -, and *. The expression contains no parentheses.

The players move alternately. On a move, a player chooses exactly one operator together with its two current operands, wraps them in parentheses, evaluates that parenthesized sub-expression, and replaces the three tokens with the resulting value. Player 1 tries to maximize the final value, and Player 2 tries to minimize it. Play continues until a single value remains.

For example, one round might proceed like this:

Initial expression: 3-6*4-7+12
Player 1's move: 3-6*(4-7)+12 → 3-6*-3+12
Player 2's move: (3-6)*-3+12 → -3*-3+12
Player 1's move: (-3*-3)+12 → 9+12
Player 2's move: (9+12) → 21

A game consists of two rounds that use the same initial (unparenthesized) expression. In the first round Player 1 moves first; in the second round Player 2 moves first. In both rounds Player 1 always maximizes and Player 2 always minimizes, regardless of who moves first. Let r1 be the result of the first round and r2 the result of the second round. If r1 > -r2, Player 1 wins; if r1 < -r2, Player 2 wins; otherwise the game is a tie. Determine the outcome assuming both players play optimally.

The first line contains an integer n, the number of test cases. Each of the next n lines contains one test case: a positive integer m (m ≤ 9) followed by an arithmetic expression. m is the number of binary operators in the expression. The only operators are +, -, and *. The - sign may be used as both a unary and a binary operator. Every binary operator is surrounded by exactly one space on each side, and there is no space after a unary -. No combination of parentheses will ever cause integer overflow or underflow.

For each test case, print Case k: (where k is the test-case number, starting at 1), followed by three lines.

• The first line reports Player 1's optimal opening move in round 1 (the round in which Player 1 moves first) and the round result r1, in the form Player 1 (move) leads to r1. Here move is the operator that is parenthesized first written together with its two operands and no spaces (for example 7+12, 45--67, or -67-3).
• The second line reports the analogous information for round 2 (the round in which Player 2 moves first): Player 2 (move) leads to r2.
• The third line is Player 1 wins, Player 2 wins, or Tie, according to the comparison of r1 and -r2.

If several operators could be parenthesized first while still achieving the optimal round result, choose the one that appears earliest in the original expression.