Mummy Madness

On an expedition across the desert you open an ancient Egyptian tomb, and the instant the door swings open the empty sand around you erupts with grumpy mummies. Your only hope is to run and stay ahead of them for as long as possible. Assuming neither you nor the mummies ever tire, how many time steps pass before a mummy finally catches you?

Model the desert as an infinite grid of squares. You and the mummies take turns, and you move first. On your turn you may move to any of the eight squares adjacent to your current square, or stay where you are. On the mummies' turn, each mummy independently moves to the one adjacent square (among its eight neighbours) that minimizes its Euclidean distance to you — equivalently, every mummy shrinks the gap by one along each axis on which it is not already aligned with you. Two mummies may occupy the same square.

A time step consists of your move followed by every mummy's move. A mummy catches you if it moves onto the square you occupy, or if you move onto a square occupied by a mummy. You play to survive as long as possible.

After how many time steps are you caught?

For instance, suppose four mummies start at $(-3, 5)$, $(3, 4)$, $(-6, -2)$ and $(1, -5)$ while you start at the origin. However you move, after four time steps the mummy that began at $(3, 4)$ reaches you, so the answer is $4$.

The input consists of several test cases. Each test case begins with an integer $n$ ($0 \le n \le 10^5$), the number of mummies. Each of the next $n$ lines contains two integers $x$ and $y$ ($|x| \le 10^6$, $|y| \le 10^6$), the starting square of one mummy. Your own starting square is $(0, 0)$, and no mummy starts there.

The last test case is followed by a line containing a single $-1$.

For each test case, print a line Case k: r, where $k$ is the test case number (starting from $1$) and $r$ is the maximum number of time steps you survive before being caught (that is, the total number of turns you get to take), or the word never if you can avoid capture forever.

Relax — after working this out you wake up safe in a hotel room. The furious mummies were only a dream. Or were they?