如果你觉得参加程序设计竞赛压力很大，不妨想象一下成为一名空中交通管制员。在关乎人命的情况下，空中交通管制员必须在不断变化的环境中专注于任务，同时还要应对各种突发事件。

考虑为在机场降落的飞机安排日程的任务。飞来的飞机会报告它们的位置、方向和速度，然后管制员必须制定一个降落计划，使所有飞机安全降落。通常，连续降落之间的时间间隔越长，降落计划就越“安全”。这段额外的时间让飞行员有机会对天气变化和其他意外情况做出反应。

幸运的是，这项调度任务的一部分可以实现自动化——这就是你需要解决的问题。你将获得飞机降落的场景。每架飞机都有一个可以安全降落的时间窗口。你必须计算出一个满足这些时间窗口的降落顺序。此外，飞机的降落时间应尽可能拉开，使得相邻两次降落之间的最小时间间隔尽可能大。例如，如果三架飞机分别在上午 10:00、10:05 和 10:15 降落，那么最小的间隔是 5 分钟（发生在头两架飞机之间）。不需要所有的间隔都相同，但最小的间隔应该尽可能大。

输入格式

输入包含多个测试用例，每个测试用例描述一个降落场景。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 8$)，表示该场景中的飞机数量。

接下来的 $n$ 行，每行包含两个整数 $a_i, b_i$，表示第 $i$ 架飞机可以安全降落的闭区间 $[a_i, b_i]$ 的起点和终点。数值 $a_i$ 和 $b_i$ 以分钟为单位，且满足 $0 \le a_i \le b_i \le 1440$。

输入以一行仅包含一个整数 $0$ 结束。

输出格式

对于输入中的每个测试用例，输出其用例编号（从 1 开始），后跟相邻降落之间可达到的最大最小时间间隔。将时间拆分为分钟和秒输出，四舍五入到最接近的秒。请遵循样例输出的格式。

样例

输入样例 1

3 
0 10 
5 15 
10 15 
2 
0 10 
10 20 
0

输出样例 1

Case 1: 7:30 
Case 2: 20:00