미라 대소동

사막을 탐험하던 중 고대 이집트 무덤을 열었더니, 문이 열리는 순간 방금 전까지 텅 비어 있던 모래밭이 심기가 잔뜩 뒤틀린 미라들로 뒤덮인다. 살아남을 유일한 방법은 최대한 오래 도망치는 것뿐이다. 당신과 미라 모두 결코 지치지 않는다고 할 때, 미라에게 붙잡히기까지 몇 번의 시간 단계가 지날까?

사막을 정사각형 칸으로 이루어진 무한 격자로 생각하자. 당신과 미라는 번갈아 움직이며, 당신이 먼저 움직인다. 당신의 차례에는 현재 칸에 인접한 여덟 칸 중 하나로 이동하거나 제자리에 머무를 수 있다. 미라의 차례에는 각 미라가 자신의 여덟 이웃 칸 중 당신과의 유클리드 거리가 가장 작아지는 칸으로 독립적으로 이동한다 — 즉 모든 미라는 아직 당신과 좌표가 일치하지 않는 각 축에서 그 차이를 1씩 줄인다. 두 미라가 같은 칸에 있어도 된다.

시간 단계는 당신의 이동에 이어 모든 미라의 이동으로 이루어진다. 미라가 당신이 있는 칸으로 이동하거나, 당신이 미라가 있는 칸으로 이동하면 붙잡힌다. 당신은 가능한 한 오래 살아남으려 한다.

몇 번의 시간 단계 후에 붙잡히는가?

예를 들어 네 미라가 각각 $(-3, 5)$, $(3, 4)$, $(-6, -2)$, $(1, -5)$에서 출발하고 당신이 원점에서 출발한다고 하자. 당신이 어떻게 움직이든, 네 번의 시간 단계가 지나면 $(3, 4)$에서 출발한 미라가 당신을 붙잡으므로 답은 $4$이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 미라의 수를 나타내는 정수 $n$ ($0 \le n \le 10^5$)으로 시작한다. 이어지는 $n$개의 줄에는 각각 두 정수 $x$와 $y$ ($|x| \le 10^6$, $|y| \le 10^6$)가 주어지며, 이는 한 미라의 시작 칸을 나타낸다. 당신의 시작 칸은 $(0, 0)$이며, 그 칸에서 출발하는 미라는 없다.

마지막 테스트 케이스 다음에는 $-1$ 하나만 있는 줄이 온다.

각 테스트 케이스마다 Case k: r 형식의 줄을 출력한다. 여기서 $k$는 테스트 케이스 번호($1$부터 시작)이고, $r$은 붙잡히기 전까지 살아남는 최대 시간 단계 수(즉 당신이 얻는 차례의 총 횟수)이다. 영원히 붙잡히지 않을 수 있다면 대신 never를 출력한다.

걱정 마시라 — 이 문제를 풀고 나면 호텔 방에서 무사히 깨어난다. 격노한 미라들은 그저 꿈이었을 뿐이다. 정말 그랬을까?