울타리

M-O는 Buy n Large 사가 만든 우주 여객선 액시엄의 바닥을 청소하는 작은 로봇이다. 오늘 밤 액시엄의 대연회장에 외부 미생물이 퍼져 바닥이 엉망이 되었고, 이 미생물을 모두 없애는 것이 M-O의 임무다.

대연회장 바닥은 한 변의 길이가 $1$인 정사각형 칸이 깔린 무한 격자다. 각 칸의 네 변과 두 대각선이 흰색 선분으로 그려져 있다. 미생물은 모두 칸의 꼭짓점 위에 있다.

청소에는 시간이 오래 걸리므로 M-O는 먼저 미생물 주위에 울타리를 세워 미생물이 다른 구역으로 퍼지는 것을 막으려 한다. M-O는 흰색 선분 위에만, 즉 칸의 변과 대각선 위에만 울타리를 놓는다. 울타리는 하나의 닫힌 경로를 이루고, 모든 미생물은 울타리 안쪽이나 울타리 위에 있어야 한다.

미생물의 위치가 주어질 때, 둘레가 가장 짧은 울타리의 둘레를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 대연회장에 있는 미생물의 수 $n$이 주어진다 ($1 \le n \le 10000$). 이어지는 $n$개의 줄에는 각각 $i$번째 미생물의 좌표 $x_i$와 $y_i$가 주어진다. 모든 좌표의 절댓값은 $10^6$ 이하이다. 좌표의 원점은 임의로 정한 칸의 꼭짓점 하나다. 서로 다른 미생물이 같은 꼭짓점에 있어도 된다.

입력의 마지막 줄에는 $0$이 하나 주어진다. 이 줄은 테스트 케이스가 아니다.

격자의 변과 대각선 위에 놓인 울타리의 둘레는 항상 $a + b\sqrt{2}$ 꼴로 유일하게 쓸 수 있다. 여기서 $a$와 $b$는 음이 아닌 정수다. 각 테스트 케이스마다 둘레가 가장 짧은 울타리의 둘레를 $a + b\sqrt{2}$라 할 때, 두 정수 $a$와 $b$를 공백으로 구분해 한 줄에 출력하라.

울타리는 닫힌 경로다. 울타리의 두 부분이 겹치면 겹친 부분의 길이는 두 번 센다.