为了尝试殖民火星，一些科学家被指派去清理这颗行星。一个名为 Marsba 的清洁机器人被建造出来，在一个巨大的火星限制区域内工作，该区域是一个 $N \times N$ 的方形网格，其中包含 $K$ ($K \le 1000$) 个不可逾越的障碍物。该区域从左到右、从上到下依次编号为 $(0, 0)$ 到 $(N-1, N-1)$，其中 $N \le 10000$。Marsba 的起始点位于左上角的网格 $(0, 0)$。Marsba 被编程为以相等的概率停留在当前网格或移动到相邻网格。（如果两个网格共享一条公共边，则称它们是相邻的。）这意味着概率被平均分配给留在当前网格以及移动到各个可用的相邻网格。具体来说，对于 Marsba 所在的网格，如果它有 $d$ 个没有障碍物的相邻网格，那么 Marsba 留在当前网格或移动到任何一个相邻网格的概率均为 $\frac{1}{d+1}$。

后来，那些科学家完全忘记了这件事。

许多年后，一位年轻人意识到了这个被遗忘的清洁机器人 Marsba 的重要性。为了进一步研究，他请求你计算 Marsba 位于满足 $x + y \ge N - 1$ 的位置 $(x, y)$ 的概率。

设该概率为最简分数形式 $p/q$，你需要分别输出 $p$ 和 $q$，并用分数斜线作为分隔符。

输入格式

输入的第一行包含一个整数 $t$ ($t \le 1000$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个正整数 $N$ 和 $K$。接下来的 $K$ 行，每行包含一个障碍物的坐标。

注意：起始点 $(0, 0)$ 没有障碍物，且所有测试用例保证所有非障碍物网格之间是连通的。

输出格式

对于每个测试用例，首先输出其编号，然后输出概率的最简分数形式。

样例

输入 1

5
3 0
3 1
1 1
3 2
1 1
2 2
3 3
1 1
1 2
2 2
5 4
1 1
1 2
2 3
3 2

输出 1

Case #1: 2/3
Case #2: 5/8
Case #3: 10/19
Case #4: 7/16
Case #5: 43/71