케이블… 우주 공간에서!

당신은 SF 소설을 쓰고 있습니다. 소설 속에서 인류는 은하 곳곳으로 퍼져 나가 여러 행성을 식민지로 삼았습니다. 성간(星間) 여행을 제외한 나머지 기술, 특히 컴퓨터는 오늘날과 비슷한 수준으로 유지하기로 했습니다. 따라서 식민 행성의 컴퓨터 네트워크도 여전히 컴퓨터 사이에 구리선이나 광케이블을 깔아 만듭니다.

현대의 컴퓨터 네트워크는 패킷 교환 방식을 사용하므로, 모든 컴퓨터 쌍마다 직접 케이블을 연결할 필요는 없습니다. 네트워크가 강하게 연결(strongly connected)되어 있기만 하면 됩니다. 즉, 임의의 두 컴퓨터 사이에 (중간의 여러 컴퓨터를 거쳐서라도) 패킷이 양방향으로 오갈 수 있는 경로가 하나라도 존재하면 충분합니다.

이 성질 덕분에 모든 컴퓨터가 서로 통신할 수 있게 하면서도 깔아야 하는 케이블의 총 길이를 최소로 줄일 수 있습니다. 새로 식민지로 삼은 행성의 모든 도시를 연결하는 네트워크를 만들 때, 중복되거나 불필요한 링크 없이 필요한 케이블의 최소 총 길이가 얼마인지 알고 싶습니다.

계산할 때 다음을 가정합니다.

행성은 완전한 구(sphere)이다.
모든 케이블은 행성 표면을 따라(대원 호, great-circle arc) 놓인다.
케이블을 방해하는 지형(강, 산맥 등)은 없다.

입력에는 행성의 지름과 도시들의 위도·경도(도, degree) 좌표가 주어집니다. 위도(latitude)는 남극의 $-90^\circ$ 에서 북극의 $+90^\circ$ 까지의 각이며, 적도가 $0^\circ$ 입니다. 경도(longitude)는 $-180^\circ$ 에서 $+180^\circ$ 까지의 각이며, 본초 자오선이 $0^\circ$ 입니다. 관례상 음수 경도는 본초 자오선의 서쪽을, 양수 경도는 동쪽을 나타냅니다.

주어진 케이블 길이 $L$ 로 모든 도시를 연결할 수 있는지 판정하세요.

입력의 첫 줄에는 데이터 집합의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어집니다. 각 데이터 집합은 다음으로 이루어집니다.

행성의 지름(킬로미터)을 나타내는 실수 $D$ ($1 \le D \le 1{,}000{,}000$)가 적힌 한 줄.
네트워크 건설에 사용할 수 있는 케이블의 총 길이(킬로미터)를 나타내는 실수 $L$ ($1 \le L \le 1{,}000{,}000$)이 적힌 한 줄.
이 행성에 있는 도시의 수를 나타내는 정수 $C$ ($1 \le C \le 100$)가 적힌 한 줄.
이어서 $C$개의 줄. 각 줄에는 한 도시의 위도와 경도(둘 다 도 단위)를 나타내는 두 실수가 "$X\ Y$" 형식으로 주어집니다. 여기서 $-90 \le X \le 90$, $-180 \le Y \le 180$입니다.

케이블… 우주 공간에서!

문제

입력

출력