{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eIn 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} .\u003cbr\u003eThen, those scientists completely forgot about it.\u003cbr\u003eMany millennia ago, a young man realizes the importance of the cleaning robot, Marsba, at the end of the forgotten.\u003cbr\u003eFor further research, he asks you to calculate the probability of Marsba’s location (x, y) satisfying x + y ≥ N - 1.\u003cbr\u003eLet 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.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer t (t ≤ 1000) specifying the number of test cases.\u003cbr\u003eFor each case, the first line contains two positive integers N and K. Each of the next K lines contains the coordinate of a barrier.\u003cbr\u003eNote that the starting point (0, 0) has no barrier and all test cases guarantee the connectivity of all lattices free of barriers."}},{"title":"Output","value":{"format":"HTML","content":"For each case output its label first, then output the probability as an irreducible fraction.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n3 0\r\n3 1\r\n1 1\r\n3 2\r\n1 1\r\n2 2\r\n3 3\r\n1 1\r\n1 2\r\n2 2\r\n5 4\r\n1 1\r\n1 2\r\n2 3\r\n3 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2/3\r\nCase #2: 5/8\r\nCase #3: 10/19\r\nCase #4: 7/16\r\nCase #5: 43/71\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}