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 N × N square grid with K (K ≤ 1000) impassable barriers. This area are numbered from (0, 0) to (N - 1, N - 1) sequentially from left to right, row by row, where N ≤ 10000. The starting point of Marsba is situated on the top left corner lattice (0, 0). 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 d adjacent lattices without impassable barriers, the probability for Marsba of remaining in the lattice or travelling to any adjacent lattice is \frac{1}{d+1} .
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 (x, y) satisfying x + y ≥ N - 1.
Let the probability be an irreducible fraction of the form p/q, you should output p and q respectively, with a fraction slash as the separator.

The first line of the input contains an integer t (t ≤ 1000) specifying the number of test cases.
For each case, the first line contains two positive integers N and K. Each of the next K lines contains the coordinate of a barrier.
Note that the starting point (0, 0) 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.

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

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

2017ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）