Radio Receiver (Small)

You have one radio receiver and you want to receive $N$ messages. Each message is transmitted at a fixed time from a fixed position. The time is measured in seconds from a reference moment, and the position is the distance from the origin in metres. You stand on a one dimensional line. The receiver picks up every message transmitted no farther than $D$ metres from your current position, where $D$ is a nonnegative real number.

You may start at any position you like, and you move at a rate of at most one metre per second. Receiving a message takes no time. Find the smallest $D$ that lets you receive every message.

The first line contains the number of test cases $C$. Each test case is given as follows.

• One line with the number of messages $N$.
• $N$ lines with the position $P$ and the transmission time $T$ of a message, separated by one space. Within one test case all transmission times are different.

Limits

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

For each test case, print one line in the form Case #x: D, where $x$ is the test case number starting at 1 and $D$ is the smallest value that lets you receive every message. The answer is always a multiple of 0.5, so print it with exactly one digit after the decimal point. Write an answer of 6 as 6.0 and an answer of 2.5 as 2.5.

In the first test case of the first example, $D = 6$ is enough. Stand at position 13 at time 2 to receive the first message, walk right to position 14 and arrive at time 3 for the second message, then walk left to position 6 and arrive at time 11 for the third message.