在 Code Jam，我们喜欢玩一个叫“Operation”的游戏。（不，它和外科手术没有任何关系；你为什么会这么想？）这个游戏使用卡片进行，每张卡片上都标有一个基本算术运算（加、减、乘或除）$O_i$ 以及一个整数右操作数 $V_i$。例如，一张卡片可能是 $+ 0$、$- -2$ 或 $/ -4$ ——请注意，操作数可以是负数或零，但除法运算的卡片永远不会以 $0$ 作为操作数。

在游戏的每一轮中，会选择一个起始整数 $S$，并摆出一组 $C$ 张卡片。玩家必须为这些卡片选择一个顺序，且每张卡片必须恰好使用一次。之后，按照顺序将这些运算应用于起始值 $S$，从而得到最终结果。

尽管卡片上的所有操作数都是整数，但运算是在有理数上执行的。例如，假设初始值为 $5$，卡片为 $+ 1$、$- 2$、$* 3$ 和 $/ -2$。如果我们按上述顺序排列，最终结果为 $(5 + 1 - 2) * 3 / (-2) = -6$。请注意，运算是按照卡片给出的顺序执行的，不考虑任何运算符优先级。另一方面，如果我们选择顺序 $- 2$、$/ -2$、$+ 1$、$* 3$，结果为 $((5 - 2) / (-2) + 1) * 3 = -3 / 2$。事实证明，该示例是这组卡片能得到的最大值。

给定一组卡片，你能算出能得到的最大最终值吗？请以不可约分数（分母为正）的形式给出结果。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $S$ 和 $C$：游戏的起始值和卡片数量。接下来有 $C$ 行，第 $i$ 行代表一张卡片，包含一个字符 $O_i$（表示运算，为 $+$, $-$, $*$, 或 $/$ 之一）和一个整数 $V_i$（表示操作数）。

输出格式

对于每个测试用例，输出一行 Case #x: y z，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 和 $z$ 是整数，使得 $y/z$ 是游戏能达到的最大最终值，$y$ 和 $z$ 除了 $1$ 和 $-1$ 外没有公约数，且 $z$ 严格大于 $0$。

数据范围

$1 \le T \le 100$ $-1,000 \le S \le 1,000$ $O_i$ 为 $+$, $-$, $*$, 或 $/$ 之一，对于所有 $i$。 $-1,000 \le V_i \le 1,000$，对于所有 $i$。 如果 $O_i = /$，则 $V_i \neq 0$，对于所有 $i$。

子任务 1 时间限制：10 秒 $1 \le C \le 15$

子任务 2 时间限制：40 秒 $1 \le C \le 1000$

样例

样例输入 1

5
1 2
- 3
* 2
5 4
+ 1
- 2
* 3
/ -2
1000 7
* -1000
* -1000
* 1000
* 1000
* 1000
* 1000
* 1000
-1 3
- -1
* 0
/ -1
0 1
+ 0

样例输出 1

Case #1: -1 1
Case #2: -3 2
Case #3:
1000000000000000000000000 1
Case #4: 1 1
Case #5: 0 1

说明

在样例 1 中，最优策略是在 $- 3$ 卡片之前使用 $* 2$ 卡片，结果为 $-1$。题目要求的唯一有理数表达式为 $-1\ 1$。

样例 2 即为题目描述第三段中提到的例子。

在样例 3 中，无论使用卡片的顺序如何，我们得到的结果都是一样的。注意，答案的分子太大，无法用 64 位整数存储。

在样例 4 中，我们能达到的最大结果是 $1$。其中一种方式是：$/ -1, * 0, - -1$。

在样例 5 中，注意答案唯一有效的表示形式是 $0\ 1$。$0\ 2$ 是无效的，因为它可以约分。$0\ -1$ 是无效的，因为分母必须为正。