你有一个无线电接收器，想要接收 $N$ 条消息。每条消息都在一个预定的时间（以自纪元以来的秒数衡量）发送。此外，每条消息都从一个预定的位置发送，该位置表示距离原点的位移（以米为单位，你在一个一维空间中）。你的无线电能够接收距离你当前位置不超过 $D$ 米的任何消息，其中 $D$ 是一个非负实数。

你可以从你选择的任何位置开始，并以最多每秒一米的速度移动。接收消息本身不需要时间。你的任务是找到允许你接收所有消息的最小 $D$。

输入格式

输入的第一行给出测试用例的数量 $C$。接下来是 $C$ 个测试用例。对于每个测试用例，包含以下内容：

• 一行，包含整数 $N$，表示消息的数量。
• $N$ 行，对应 $N$ 条消息，其中每行包含两个由空格隔开的整数 $P$ 和 $T$。$P$ 是发送消息的位置，$T$ 是发送该消息的时间（消息的发送时间各不相同）。

输出格式

对于每个测试用例，输出一行，包含 "Case #$x$: "，其中 $x$ 是测试用例的编号，后跟允许你接收所有消息的最小值 $D$。与标准答案的相对或绝对误差不超过 $10^{-9}$ 的答案将被视为正确。

数据范围

• $1 \le C \le 100$
• $1 \le N \le 1000$

小数据集 (15 分)

• $0 \le P \le 1000$
• $0 \le T \le 1000$

小数据集 (25 分)

• $0 \le P \le 10^9$
• $0 \le T \le 10^9$

样例

样例输入 1

3
3
7 2
20 3
0 11
2
6 5
6 3
4
5 3
2 1
9 4
7 2

样例输出 1

Case #1: 6
Case #2: 0
Case #3: 2.00

说明

对于测试用例 1，以下是 $D = 6$ 的一种可能方案。在时间 2 从位置 13 开始以获取消息 0。然后向右步行到位置 14，在时间 3 到达以获取消息 1。然后向左步行到位置 6，在时间 11 到达以获取消息 2。