도망쳐라

피라미드에서 마주치게 될 함정 중 하나는 큰 방(Large Room)에 있다. 바닥에는 작은 구멍이 아주 많이 뚫려 있다. 언뜻 보기에는 전혀 위험해 보이지 않지만, 일단 작동하면 아주 뜨거운 자바(java)를, 아니 실례, 용암(lava)을 뿜어낸다. 안타깝게도 석관(Sarcophagus)이 있는 중앙 방(Center Room)으로 가는 알려진 모든 경로에는 이 함정을 작동시키는 방아쇠가 놓여 있으며, 함정을 해제할 방법은 없다. 다행히 모든 구멍의 위치는 미리 기록해 두었다. 이제 큰 방 안에서 모든 구멍으로부터 가능한 한 멀리 떨어진 지점, 정확히는 가장 가까운 구멍까지의 거리가 최대가 되는 지점을 찾아야 한다. 그 지점이 방에서 가장 안전한 곳이며, 고고학자는 그곳에 숨어야 한다.

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 X, Y, M이 공백으로 구분되어 주어진다 (1 ≤ X, Y ≤ 10000, 1 ≤ M ≤ 1000). X와 Y는 직사각형 모양인 큰 방의 가로·세로 길이로, 방의 두 대각 꼭짓점은 (0, 0)과 (X, Y)이다. M은 구멍의 개수이다. 이어지는 M개의 줄에는 각각 한 구멍의 좌표를 나타내는 두 정수 Ui와 Vi가 주어진다 (0 ≤ Ui ≤ X, 0 ≤ Vi ≤ Y). 여러 구멍이 같은 위치에 있을 수도 있다.

각 테스트 케이스에 대해, 방의 경계를 포함한 내부의 모든 점 중에서 가장 가까운 구멍까지의 거리를 최대로 만드는 값을 d*라 하자. 가장 안전한 점 자체는 유일하지 않을 수 있고 그 좌표가 무리수가 될 수도 있으므로, 대신 항상 유리수가 되는 가장 안전한 거리의 제곱 (d*)²의 정확한 값을 출력한다. 이 값을 기약분수 p/q (q ≥ 1, gcd(p, q) = 1) 형태로 한 줄에 출력하되, q = 1이면 정수 p만 출력한다.