Run Away

One of the traps waiting for us in the Pyramid sits in the Large Room. A great many small holes have been drilled into the floor. At first glance they look completely harmless, but once triggered they start to spray out very hot java -- uh, pardon, lava. Unfortunately every known path to the Center Room (where the Sarcophagus rests) steps on a trigger that arms the trap, and there is no way to disarm it. Fortunately the positions of all the holes have been carefully recorded. Your job is to find the spot in the Large Room that lies as far as possible from the holes -- precisely, the spot that maximizes the distance to its nearest hole. That spot is the safest place in the entire room, and the archaeologist should hide there.

The first line contains the number of test cases T. Each test case begins with a line holding three integers X, Y, and M separated by spaces (1 ≤ X, Y ≤ 10000, 1 ≤ M ≤ 1000). X and Y are the side lengths of the rectangular Large Room, whose opposite corners are (0, 0) and (X, Y). M is the number of holes. Each of the next M lines contains two integers Ui and Vi (0 ≤ Ui ≤ X, 0 ≤ Vi ≤ Y), the coordinates of one hole. Several holes may share the same position.

For each test case, let d* be the largest value, taken over every point inside the room (its boundary included), of the distance from that point to the nearest hole. Because the safest point itself is not always unique and its coordinates may be irrational, output the exact value of (d*)² instead -- the squared safest distance, which is always a rational number. Print it on its own line as a reduced fraction p/q with q ≥ 1 and gcd(p, q) = 1; if q = 1, print only the integer p.