I. 미라 대소동

2011 A\(CM-IC\)PC 월드 파이널 기간에 사막으로 소풍을 갔다가 당신은 오래된 이집트 무덤을 발견한다. 안타깝게도 무덤을 여는 것은 나쁜 생각이었다. 조금 전까지만 해도 텅 빈 사막이었던 곳이 갑자기 심술 난 미라들로 우글거리는 사막이 되어 버렸다(수천 년의 평화로운 잠에서 갑자기 깨어난다면 당신도 심술이 날 것이다).^{2} 이 살기등등한 미라 떼 앞에서 유일한 희망은 도망쳐서 잡히기 전에 탈출하는 것이다. 문제는 이것이다. 당신도 미라들도 결코 지치지 않는다고 할 때, 미라가 당신을 잡을 때까지 얼마나 걸릴까? 사막을 정사각형 칸들의 격자로 모델링한다. 당신과 미라들은 격자 위에서 번갈아 움직인다. 당신이 먼저 움직인다. 당신의 차례에는 현재 위치에 인접한 여덟 칸 중 하나로 이동하거나 가만히 있을 수 있다. 미라들의 차례에는 각 미라가 (당신과 모든 미라가 각자 칸의 중심에 서 있다고 가정하고 유클리드 거리로 측정하여) 당신에게 가장 가까워지는 인접 칸으로 이동한다. 두 미라가 같은 칸을 차지할 수도 있다. 한 시간 단계는 당신의 이동과 그다음 미라들의 이동으로 이루어진다. 미라가 당신이 있는 칸으로 이동하거나 당신이 미라가 차지한 칸으로 이동하면 미라에게 잡힌다. 물론 당신은 가능한 한 오래 잡히지 않으려 한다. 몇 번의 시간 단계 후에 잡히게 될까? 그림 I.1: 미라 추격전 그림은 미라 네 마리에게 쫓길 때 벌어질 수 있는 일을 보여 준다. H로 표시된 칸이 당신의 초기 위치이고, M으로 표시된 칸들이 미라의 초기 위치이다. 네 번의 시간 단계 후, 당신의 초기 위치 기준 (3, 4)에서 시작한 미라에게 잡힌다. ^{2}다행히 이 문제를 풀고 나서 당신은 플로리다의 호텔 방에서 무사히 깨어났다. 분노한 미라들은 그저 꿈이었다. 아니, 정말 꿈이었을까?

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 사막에 있는 미라의 수를 나타내는 정수 \(n\) (\(0 \le n \le 10^{5}\))으로 시작한다. 다음 \(n\)개의 줄에는 각각 두 정수 \(x\)와 \(y\)가 주어지며, 이는 사막의 좌표 (x, y)에 처음에 미라가 있음을 나타낸다. \(x\)와 \(y\)의 절댓값은 모두 \(10^{6}\) 이하이다. 당신의 시작 위치는 (0, 0)이고, 이 위치에서 시작하는 미라는 없다. 마지막 테스트 케이스 다음에는 numb\(er - 1\), 즉 −1이 적힌 줄이 주어진다.

각 테스트 케이스마다 테스트 케이스 번호와 함께, 잡힐 때까지의 최대 시간 단계 수(당신이 갖는 전체 차례 수로 측정)를 출력하거나, 무한히 잡히지 않을 수 있으면 “never”를 출력한다. 샘플 출력의 형식을 따른다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2011