현장 학습

한 초등학교에서 온 N명, 즉 교사 한 명과 아이 N-1명이 현장 학습을 나왔다. 이들은 단위 칸으로 이루어진 무한한 이차원 격자 형태의 풀밭을 탐험하고 있다. 현재 각 사람은 칸 하나를 차지하고 있으며, 같은 칸에 여러 사람이 있을 수도 있다.

집에 갈 시간이 되면 교사와 아이들은 모두 하나의 칸에 모여야 한다. 버스가 어디에서든 이들을 태울 수 있으므로 어느 칸인지는 중요하지 않다. 아이들은 더 쉽게 모일 수 있게 해 주는 다음 알고리즘을 배웠다.

• 교사는 1번 사람이고, 아이들은 2번부터 N번까지 번호가 매겨져 있다.

• 한 사람이 취하는 행동은 현재 칸과 적어도 하나의 변 또는 모서리를 공유하는 8개의 칸 중 하나로 이동하거나, 현재 칸에 그대로 머무르는 것이다.

• 현장 학습 종료 신호가 울리면, 교사는 N명 모두가 같은 칸에 있는지 확인한다. 모두 같은 칸에 있다면 추가 행동은 필요하지 않다. 그렇지 않다면 교사가 한 턴을 시작한다.

• 먼저 교사가 위에서 설명한 행동을 취한다. 이동할지, 이동한다면 어디로 갈지는 교사가 결정한다.

• 그런 다음 2번 아이부터 시작하여 N번 아이까지 차례로 각 아이가 행동을 취한다. i번째 아이는 (i-1)번째 사람이 행동을 취할 때까지 자신의 행동을 취하지 않는다. 아이들의 행동은 결정적이다. i번째 아이는 자신의 칸 중심과 (i-1)번째 사람의 칸 중심 사이의 거리를 최소화하는 선택지를 반드시 골라야 한다. 이 선택에는 절대 모호함이 없다. 9개의 선택지 중 하나만이 그 거리를 최소화한다.

• 턴이 끝나면 교사는 모든 사람이 같은 칸에 있는지 다시 확인한다. 같은 칸에 있지 않다면 또 다른 턴이 시작되며, 모두가 한 칸에 모일 때까지 이를 계속한다.

교사가 턴 수를 최소화하도록 선택한다면, 그 턴 수는 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

2 ≤ N ≤ 10. 모든 i에 대해, 0 ≤ $R_{i}$ ≤ 8. 모든 i에 대해, 0 ≤ $C_{i}$ ≤ 8.

테스트 세트 2 (비공개)

2 ≤ N ≤ $10^{4}$. 모든 i에 대해, 0 ≤ $R_{i}$ ≤ $10^{9}$. 모든 i에 대해, 0 ≤ $C_{i}$ ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N이 있는 한 줄로 시작하며, N은 현장 학습에 참여한 사람의 수이다. 그다음 N개의 줄이 더 주어진다. 이 중 i번째 줄은 i번째 사람을 나타내며 두 정수 $R_{i}$와 $C_{i}$가 주어진다. 이는 i번째 사람이 처음 차지하고 있는 칸의 행 번호와 열 번호이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 위에서 설명한 대로 필요한 턴 수로 가능한 최솟값이다.

예제 케이스 #1에서 교사는 (3, 2), 즉 3행 2열에 있다. 아이 2는 (0, 2)에 있고, 아이 3는 (0, 0)에 있다. 교사가 사용할 수 있는 최적 전략 중 하나는 다음과 같다.

• 턴 1:

• (2, 2)로 이동한다.

• 아이 2가 (1, 2)로 이동한다.

• 아이 3가 (1, 1)로 이동한다.

• 턴 2:

• (1, 2)로 이동한다.

• 아이 2는 (1, 2)에서 제자리에 머문다.

• 아이 3가 (1, 2)로 이동한다. 이제 모두가 같은 칸에 있다.

예제 케이스 #2에서는 교사와 두 아이가 같은 칸에서 시작하므로 턴이 필요하지 않다.

예제 케이스 #3에서는 교사가 제자리에 머무르면 첫 턴이 끝날 때까지 모든 아이가 교사의 칸으로 이동한다.

예제 케이스 #4에서는 교사가 대각선 방향으로 네 번 이동하여 (4, 4)에 도달해야 한다.

예제 케이스 #5에서는 교사가 먼저 (1, 1)로 이동해야 한다. 그러면 아이 2, 3, 4가 모두 (1, 2)로 이동한다. 이제 모든 아이가 같은 칸에 있더라도 교사는 그 칸에 없으므로 또 다른 턴을 시작해야 한다는 점에 유의하라. 두 번째 턴에는 교사가 (1, 2)로 이동해 아이들과 합류할 수 있으며, 아이들은 움직이지 않는다.