A Careful Approach

프로그래밍 콘테스트에 참가하는 것도 힘들겠지만, 항공 교통 관제사가 되어 보는 것은 더 힘들다. 사람의 목숨이 걸려 있는 만큼, 관제사는 계속 변하는 상황과 예상치 못한 사건에 대처하면서 업무에 집중해야 한다.

공항에 착륙할 비행기들의 일정을 짜는 일을 생각해 보자. 진입하는 비행기들은 자신의 위치, 방향, 속도를 보고하고, 관제사는 모든 비행기를 안전하게 착륙시키는 착륙 일정을 짜야 한다. 일반적으로 연속한 착륙 사이의 간격이 클수록 착륙 일정은 더 "안전"하다. 이 여유 시간 덕분에 조종사는 변하는 날씨와 다른 돌발 상황에 대응할 수 있다.

다행히 이 일정 조정 업무의 일부는 자동화할 수 있다. 여기에서 여러분이 필요하다. 여러분에게는 비행기 착륙 시나리오가 주어진다. 각 비행기에는 안전하게 착륙할 수 있는 시간 구간이 있다. 여러분은 이 시간 구간을 지키면서 모든 비행기를 착륙시킬 순서를 계산해야 한다. 또한, 착륙 시각들을 최대한 벌려서 연속한 착륙 사이의 최소 시간 간격이 최대가 되게 해야 한다. 예를 들어 세 비행기가 오전 10:00, 오전 10:05, 오전 10:15에 착륙한다면 가장 작은 간격은 5분이며, 이는 처음 두 비행기 사이에서 발생한다. 모든 간격이 같을 필요는 없지만, 가장 작은 간격은 최대가 되어야 한다.

입력 파일에는 여러 착륙 시나리오의 설명으로 이루어진 여러 테스트 케이스가 들어 있다. 각 테스트 케이스는 시나리오에 있는 비행기의 수를 나타내는 정수 n (2 ≤ n ≤ 8)이 있는 한 줄로 시작한다. 그다음 n개의 줄이 이어지며, 각 줄에는 i번째 비행기가 안전하게 착륙할 수 있는 닫힌 구간 [ai, bi]의 시작과 끝을 나타내는 두 정수 ai, bi가 있다. ai와 bi는 분 단위로 주어지며 0 ≤ ai ≤ bi ≤ 1440을 만족한다.

입력은 정수 0 하나가 있는 줄로 끝난다.

입력의 각 테스트 케이스마다 케이스 번호(1부터 시작)를 출력한 뒤 연속한 착륙 사이의 최소 달성 가능 시간 간격을 출력한다. 시간을 분과 초로 나누어 가장 가까운 초로 반올림하여 출력한다. 출력 형식은 예시 출력을 따른다.