라디오 수신기

라디오 수신기로 메시지 $N$개를 받으려고 한다. 각 메시지는 정해진 시각에, 정해진 위치에서 송신된다. 시각의 단위는 초이고, 위치는 원점에서 떨어진 거리를 미터로 나타낸 값이다. 당신은 직선 위에 있으므로 위치는 실수 하나로 정해진다. 메시지가 송신되는 순간에 그 송신 위치와 당신 사이의 거리가 $D$미터 이하이면 그 메시지를 받는다. $D$는 음이 아닌 실수이다.

시작 위치는 마음대로 고를 수 있고, 이동 속도는 초당 최대 1미터이다. 메시지를 받는 데는 시간이 걸리지 않는다. 모든 메시지를 받을 수 있는 가장 작은 $D$를 구하라.

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

각 테스트 케이스의 첫째 줄에는 메시지의 개수 $N$이 주어진다. 이어지는 $N$개의 줄에는 정수 $P$와 $T$가 공백 하나로 구분되어 주어진다. $P$는 메시지가 송신된 위치이고, $T$는 메시지가 송신된 시각이다. 한 테스트 케이스 안에서 송신 시각은 모두 다르다.

제한

• $1 \le C \le 100$
• $1 \le N \le 1000$
• $0 \le P \le 10^9$
• $0 \le T \le 10^9$

각 테스트 케이스마다 한 줄에 Case #x: D 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $D$는 모든 메시지를 받을 수 있는 가장 작은 $D$이다.

답은 항상 $0.5$의 배수이므로 소수점 아래 한 자리까지만 출력한다. 예를 들어 답이 6이면 6.0, 답이 1.5이면 1.5로 쓴다.

첫 번째 예제의 첫 테스트 케이스는 $D = 6$이면 충분하다. 시각 2에 위치 13에서 출발해 7에서 송신된 메시지를 받는다. 오른쪽으로 걸어 시각 3에 위치 14에 도착해 20에서 송신된 메시지를 받는다. 그다음 왼쪽으로 걸어 시각 11에 위치 6에 도착해 0에서 송신된 메시지를 받는다.