화초에 물 주기 (라지)

온실에 물을 줘야 하는 화초가 여러 개 있다. 화초 하나가 차지하는 영역은 원이고, 어떤 두 화초도 서로 겹치거나 접하지 않는다.

스프링클러를 두 대 산다. 스프링클러 한 대는 반지름이 $R$인 원 안의 모든 지점에 물을 뿌린다. 한 대는 아침에 돌고 다른 한 대는 밤에 돈다. 화초가 물을 충분히 받으려면 그 화초의 영역 전체가 아침에 젖거나, 영역 전체가 밤에 젖어야 한다. 즉 화초를 나타내는 원은 스프링클러가 물을 뿌리는 두 원 중 적어도 하나에 완전히 들어가야 한다.

스프링클러는 천장에 달기 때문에 스프링클러의 위치가 화초의 영역 안이어도 된다.

각 화초의 중심과 반지름이 주어진다. 스프링클러 두 대를 알맞게 놓아 모든 화초에 물을 줄 수 있는 최소 반지름 $R$을 구하라.

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

각 테스트 케이스는 다음 형식이다.

• 첫째 줄에 화초의 개수 $N$이 주어진다.
• 다음 $N$개 줄에 화초 하나의 정보가 정수 세 개 X Y R로 주어진다. $(X, Y)$는 화초의 중심이고 $R$은 화초의 반지름이다.

제한

• 입력의 모든 수는 정수다.
• $1 \le X \le 1000$
• $1 \le Y \le 1000$
• $1 \le R \le 100$
• $1 \le C \le 30$
• $1 \le N \le 40$
• 어떤 두 화초도 서로 겹치거나 접하지 않는다.

각 테스트 케이스마다 Case #x: R 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $R$은 스프링클러의 최소 반지름이다. $R$은 반올림해서 소수점 아래를 정확히 네 자리 출력한다.

테스트 데이터의 모든 정답은 반올림 경계에서 $10^{-5}$ 이상 떨어져 있다. 오차가 $10^{-6}$ 이하인 풀이는 같은 값을 출력한다.

예제의 첫 번째 테스트 케이스에서는 $(20, 15)$를 중심으로 하는 반지름 7 이상의 스프링클러가 앞의 두 화초에 물을 주고, 반지름 3인 스프링클러가 $(40, 10)$의 화초에 물을 준다.

두 번째 테스트 케이스에서는 두 스프링클러 중 하나의 반지름이 적어도 8이어야 한다. $(30, 10)$의 화초도 두 원 중 하나에 완전히 들어가야 한다.