무전 수신기 (Small)

무전 수신기 하나로 메시지 $N$개를 모두 받으려고 한다. 각 메시지는 정해진 시각에 정해진 위치에서 송신된다. 시각은 기준 시각에서 흐른 시간을 초로 잰 값이고, 위치는 원점에서 떨어진 거리를 미터로 잰 값이다. 당신은 1차원 직선 위에 있다. 수신기는 현재 위치에서 $D$미터를 넘지 않는 곳에서 송신된 메시지를 모두 받는다. $D$는 음이 아닌 실수다.

시작 위치는 원하는 대로 고를 수 있고, 이동 속도는 초당 최대 1미터다. 메시지를 받는 동작 자체에는 시간이 들지 않는다. 메시지를 모두 받을 수 있는 가장 작은 $D$를 구하여라.

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

• 첫 줄에 메시지의 개수 $N$이 주어진다.
• 이어지는 $N$개 줄에 메시지의 위치 $P$와 송신 시각 $T$가 공백 하나를 사이에 두고 주어진다. 한 테스트 케이스 안에서 송신 시각은 모두 다르다.

제한

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

각 테스트 케이스마다 Case #x: D 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $D$는 메시지를 모두 받을 수 있는 가장 작은 값이다. 답은 항상 0.5의 배수이므로 소수점 아래 한 자리까지 정확히 적는다. 답이 6이면 6.0, 2.5면 2.5로 출력한다.

첫 번째 예제의 첫 테스트 케이스는 $D = 6$이면 충분하다. 시각 2에 위치 13에 서서 첫 메시지를 받고, 오른쪽으로 걸어 시각 3에 위치 14에서 두 번째 메시지를 받고, 왼쪽으로 걸어 시각 11에 위치 6에서 세 번째 메시지를 받는다.