등불

헨젤과 그레텔의 부모는 밤에 숲을 가로질러 아이들과 산책을 하려고 합니다. 가족 산책은 오랜 전통이지만, 아이들은 부모보다 걸음이 느리고 어둠 속에 도사린 맹수들이 무서워 이 산책이 달갑지 않습니다.

밤길을 안내해 줄 도구가 없는 헨젤과 그레텔은 낮 동안 숲에 등불을 가져와 나무에 매달아 두는 방법으로 준비합니다. 밤이 되면 각 등불은 그 나무를 중심으로 반지름 r인 원 모양의 빛을 비춥니다(그림자는 고려하지 않습니다). 아이들은 빛이 닿는 영역 안에 머무는 한 안전합니다. 서로 충분히 가까운 나무들에 등불을 매달면 두 빛의 원이 맞닿거나 겹쳐서 여러 나무를 아우르는 하나의 연결된 빛 구역이 만들어지고, 그 안에서 아이들은 안전하게 이동할 수 있습니다.

먼저 헨젤과 그레텔은 하나의 연결된 빛 구역 안에서 최대 몇 그루의 나무를 함께 밝힐 수 있는지 알고 싶어 합니다. 즉, 모든 나무에 등불을 매달았을 때 하나의 연결된 구역에 속하는 나무 수의 최댓값입니다. 이 가장 큰 구역이 두 그루 이상의 나무로 이루어진다면, 그러한 구역은 유일합니다.

그 구역의 모든 나무에 등불을 매달 수도 있지만, 두 나무가 매우 가까우면 한 나무의 빛이 이미 다른 나무를 비추고 있을 수 있으므로 더 적은 수의 등불로도 충분할 수 있습니다. 무게와 빛 공해, CO2를 줄이기 위해 아이들은 가장 큰 구역의 모든 나무를 밝히면서도 밝혀진 영역이 연결된 상태를 유지하여 어떤 나무에서든 어둠을 밟지 않고 다른 어떤 나무로도 갈 수 있도록 하는 최소 등불 수도 알고 싶어 합니다(그림 1 참고).

그림 1: 두 가지 나무 배치 예시. 왼쪽에서는 하나의 빛 구역에 최대 세 그루가 들어갈 수 있으며, 잘 배치한 등불 하나로 세 그루를 모두 밝힐 수 있습니다. 오른쪽에서는 한 구역에 최대 네 그루가 들어갈 수 있으며, 오른쪽 두 나무에 등불을 매다는 것이 가장 효율적입니다. 두 배치 모두에서 한 나무는 다른 나무들과 너무 멀어 같은 구역을 이루지 못합니다.

• 첫 번째 줄에는 테스트 케이스의 개수 n (0 < n ≤ 100)이 주어집니다.
• 각 테스트 케이스는 다음으로 구성됩니다.
  • 등불이 만드는 원 모양 빛의 반지름 r (0 < r ≤ 100)이 적힌 한 줄.
  • 숲에 있는 나무의 수 t (1 < t ≤ 20)가 적힌 한 줄.
  • 각 나무의 위치를 정수 좌표 x, y로 나타낸 t개의 줄(정수 좌표).

각 테스트 케이스마다 공백으로 구분된 두 정수를 한 줄에 출력합니다. 첫 번째 정수는 만들 수 있는 가장 큰 연결된 빛 구역의 크기(밝혀지는 나무의 수)이고, 두 번째 정수는 그 구역의 모든 나무를 밝히면서 밝혀진 영역을 연결된 상태로 유지하는 데 필요한 등불의 최소 개수입니다.