Operation (Small)

A card game called Operation is played with cards. Each card holds one arithmetic operation $O_i$ (addition, subtraction, multiplication, or division) and one integer $V_i$, the right operand of that operation. A card can read + 0, - -2, or / -4. An operand can be negative or zero, but a division card never has 0 as its operand.

In one round you get a starting integer $S$ and a set of $C$ cards. You choose an order for the cards and use each card exactly once. The operations are applied to $S$ in that order, and the last value is the result of the round.

Every operand on a card is an integer, but the operations run on rational numbers. Suppose the starting value is 5 and the cards are + 1, - 2, * 3, / -2. Used in that order the result is $(5 + 1 - 2) \times 3 / (-2) = -6$. Operator precedence does not apply, the cards are applied in the order you choose. Used in the order - 2, / -2, + 1, * 3 the result is $((5 - 2) / (-2) + 1) \times 3 = -3/2$, which is the largest value this set of cards can reach.

Given a set of cards, find the largest final value. Write it as an irreducible fraction with a positive denominator.

The first line has the number of test cases $T$. Each test case begins with a line holding two integers $S$ and $C$, the starting value and the number of cards. The next $C$ lines describe the cards. The $i$-th of those lines has one character $O_i$ for the operation and one integer $V_i$ for the operand.

Limits

• $1 \le T \le 100$
• $-1000 \le S \le 1000$
• $O_i$ is one of +, -, *, / for all $i$.
• $-1000 \le V_i \le 1000$ for all $i$.
• If $O_i$ is /, then $V_i \ne 0$.
• $1 \le C \le 15$

For each test case, print one line Case #x: y z, where $x$ is the test case number starting from 1, and $y$ and $z$ are integers such that $y/z$ is the largest final value of the game, $y$ and $z$ have no common divisor other than 1 and -1, and $z$ is strictly greater than 0.

In the first sample case, playing * 2 before - 3 gives -1, and the required form of that value is -1 1.

The second sample case is the one described in the statement.

In the third sample case the order of the cards does not change the result. The numerator of the answer does not fit in a 64-bit integer.

In the fourth sample case the largest result is 1, reached for example by / -1, * 0, - -1.

In the fifth sample case 0 1 is the only valid answer. 0 2 can be reduced, and 0 -1 has a denominator that is not positive.