화분에 물 주기

온실에 물을 주어야 하는 화분이 여러 개 있다. 각 화분이 차지하는 영역은 원이고, 어떤 두 화분도 서로 겹치거나 맞닿지 않는다.

스프링클러를 두 대 산다. 각 스프링클러는 반지름이 $R$인 원 안의 모든 것에 물을 뿌린다.

한 대는 아침에 돌고 다른 한 대는 밤에 돈다. 어떤 화분이 물을 충분히 받았다고 인정하려면 그 화분의 영역 전체가 아침에 물을 받거나, 영역 전체가 밤에 물을 받아야 한다. 즉 화분을 나타내는 각 원은 스프링클러가 물을 뿌리는 두 원 중 하나에 완전히 들어가야 한다.

화분의 위치와 반지름이 주어진다. 스프링클러 두 대를 놓아 모든 화분에 물을 줄 수 있는 최소 반지름 $R$를 구하라. 스프링클러는 천장에 설치하므로 스프링클러의 위치가 화분 영역 안이어도 된다.

첫 줄에 테스트 케이스의 개수 $C$가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 화분의 개수 $N$이 주어진다.
• 다음 $N$개의 줄에 화분 하나마다 세 정수 $X$, $Y$, $R$가 주어진다. $(X, Y)$는 화분 중심의 좌표이고 $R$는 그 화분의 반지름이다.

제한

• 입력의 모든 수는 정수다.
• $1 \le C \le 10$
• $1 \le N \le 20$
• $1 \le X \le 1000$
• $1 \le Y \le 1000$
• $1 \le R \le 100$
• 어떤 두 화분도 서로 겹치거나 맞닿지 않는다.

각 테스트 케이스마다 한 줄에 Case #x: R 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고 $R$는 스프링클러의 최소 반지름이다.

반지름은 소수점 아래 여섯째 자리까지 반올림해서 출력한다. 최소 반지름이 7이면 7.000000을 출력한다.

예제의 첫 번째 케이스에서는 (20, 15)를 중심으로 놓은 반지름 7 이상의 스프링클러가 앞의 두 화분에 물을 준다. (40, 10)에 있는 화분은 반지름이 3 이상이면 덮인다.

두 번째 케이스에서는 두 스프링클러 중 하나의 반지름이 8 이상이어야 한다. (30, 10)에 있는 화분도 두 스프링클러 중 하나에 완전히 덮여야 한다.