연산 게임 (Small)

문제

카드로 하는 Operation이라는 게임이 있다. 카드마다 사칙연산 중 하나인 연산 $O_i$ (덧셈, 뺄셈, 곱셈, 나눗셈)와 그 연산의 오른쪽 피연산자인 정수 $V_i$ 가 하나씩 적혀 있다. 예를 들어 + 0, - -2, / -4 같은 카드가 있다. 피연산자는 음수나 0일 수 있지만, 나눗셈 카드의 피연산자는 0이 아니다.

한 라운드에서는 시작 정수 $S$ 와 카드 $C$ 장을 받는다. 카드의 순서를 정하고 각 카드를 정확히 한 번씩 쓴다. 정한 순서대로 $S$ 에 연산을 적용해서 마지막 값을 얻는다.

카드에 적힌 피연산자는 모두 정수지만 연산은 유리수 위에서 이루어진다. 시작 값이 5이고 카드가 + 1, - 2, * 3, / -2라고 하자. 적힌 순서대로 쓰면 결과는 $(5 + 1 - 2) \times 3 / (-2) = -6$ 이다. 연산자 우선순위는 따지지 않고 카드 순서대로만 적용한다. - 2, / -2, + 1, * 3 순서로 쓰면 결과는 $((5 - 2) / (-2) + 1) \times 3 = -3/2$ 이고, 이 카드 집합으로 만들 수 있는 최댓값이다.

카드 집합이 주어질 때 만들 수 있는 최종 값의 최댓값을 구한다. 답은 분모가 양수인 기약분수로 나타낸다.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 시작 값 $S$ 와 카드의 수 $C$ 가 공백으로 구분되어 주어진다. 이어지는 $C$ 개의 줄에 카드가 한 장씩 주어진다. $i$ 번째 줄에는 연산을 나타내는 문자 $O_i$ 와 피연산자인 정수 $V_i$ 가 주어진다.

제한

$1 \le T \le 100$
$-1000 \le S \le 1000$
모든 $i$ 에 대해 $O_i$ 는 +, -, *, / 중 하나다.
모든 $i$ 에 대해 $-1000 \le V_i \le 1000$
$O_i$ 가 /이면 $V_i \ne 0$
$1 \le C \le 15$

출력

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 와 $z$ 는 $y/z$ 가 게임에서 얻을 수 있는 최댓값이 되는 정수다. $y$ 와 $z$ 의 공약수는 1과 -1뿐이어야 하며, $z$ 는 0보다 커야 한다.

힌트

예제의 첫 번째 케이스에서는 * 2를 - 3보다 먼저 쓰면 -1이 되고, 조건에 맞게 나타내면 -1 1이다.

두 번째 케이스는 문제에서 설명한 예와 같다.

세 번째 케이스는 카드를 어떤 순서로 써도 결과가 같다. 답의 분자는 64비트 정수에 들어가지 않는다.

네 번째 케이스에서 얻을 수 있는 최댓값은 1이다. / -1, * 0, - -1 순서로 쓰면 된다.

다섯 번째 케이스의 답은 0 1뿐이다. 0 2는 약분이 되고, 0 -1은 분모가 양수가 아니다.