#216952. [ICPC 2017 Shenyang R] Wandering Robots

In an attempt to colonize Mars, some scientists were tasked with cleaning the planet. A cleaning robot, Marsba, was build with a huge restricted area in the Mars as a massive square grid with () impassable barriers. This area are numbered from to sequentially from left to right, row by row, where . The starting point of Marsba is situated on the top left corner lattice . Marsba had instructions to program him with equal probability of remaining in the same lattice or travelling to an adjacent one. (Two lattices are said to be adjacent if they share a common edge.) This meant an equal probability being split equally between remaining in the lattice and the number of available routes.

Specifically, for the lattice Marsba located in which has adjacent lattices without impassable barriers, the probability for Marsba of remaining in the lattice or travelling to any adjacent lattice is .

Then, those scientists completely forgot about it.

Many millennia ago, a young man realizes the importance of the cleaning robot, Marsba, at the end of the forgotten.For further research, he asks you to calculate the probability of Marsba’s location satisfying .

Let the probability be an irreducible fraction of the form , you should output and respectively, with a fraction slash as the separator.

The first line of the input contains an integer () specifying the number of test cases.

For each case, the first line contains two positive integers and . Each of the next lines contains the coordinate of a barrier.

Note that the starting point has no barrier and all test cases guarantee the connectivity of all lattices free of barriers.

For each case output its label first, then output the probability as an irreducible fraction.

样例输入 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