Radio Receiver

You have a radio receiver and want to receive $N$ messages. Each message is sent at a fixed time, measured in seconds, from a fixed position, measured in meters from the origin. You stand on a line, so your position is a single real number. You receive a message if, at the moment it is sent, the distance between you and its sending position is at most $D$ meters. $D$ is a nonnegative real number.

You choose your starting position freely and you move at a speed of at most one meter 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$.

The first line of each test case contains the number of messages, $N$. Each of the next $N$ lines contains two integers $P$ and $T$ separated by one space. $P$ is the position the message is sent from and $T$ is the time it is sent. Within one test case all sending times are distinct.

Limits

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

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 $D$ that receives every message.

The answer is always a multiple of $0.5$, so print exactly one digit after the decimal point. An answer of 6 is written 6.0 and an answer of 1.5 is written 1.5.

In the first test case of the first example, $D = 6$ is enough. Start at position 13 at time 2 and receive the message sent from 7. Walk right and arrive at position 14 at time 3 to receive the message sent from 20. Then walk left and arrive at position 6 at time 11 to receive the message sent from 0.