럭비

아주 먼 행성에서는 경계가 없는 이차원 데카르트 좌표계에서 럭비를 한다. 선수들은 정수 격자점만 차지할 수 있으며, 네 기본 방향 중 어느 방향으로든 인접한 격자점으로 이동할 수 있다. 구체적으로 선수가 현재 점 (X, Y)에 있다면 한 번의 이동으로 점 (X+1, Y), (X-1, Y), (X, Y+1), (X, Y-1) 중 하나로 이동할 수 있다.

경기가 끝난 뒤 N명의 선수가 좌표계 곳곳에 흩어져 있으며, 각 격자점은 비어 있거나 한 명 이상의 선수가 차지하고 있다. 선수들은 사진을 찍기 위해 모여서, 각 점에 선수 한 명씩 위치하고 차지한 모든 점이 서로 인접하는 N개 격자점의 완벽한 수평선을 만들려고 한다. 형식적으로, 선수들은 어떤 좌표 X와 Y에 대해 격자점 (X, Y), (X+1, Y), (X+2, Y), ..., (X+N-1, Y)를 차지하도록 이동해야 한다. 좌표계에서 선의 위치를 자유롭게 선택할 수 있고 선수들의 순서가 중요하지 않을 때, 완벽한 선을 만들기 위해 선수들이 이동해야 하는 총 이동 횟수의 최솟값은 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

테스트 세트 1

시간 제한: 20초. 1 ≤ N ≤ 10. -500 ≤ $X_{i}$ ≤ 500. -500 ≤ $Y_{i}$ ≤ 500.

테스트 세트 2

시간 제한: 40초. 최대 10개의 케이스에 대해 1 ≤ N ≤ $10^{5}$. 나머지 케이스에 대해 1 ≤ N ≤ $10^{4}$. -$10^{9}$ ≤ $X_{i}$ ≤ $10^{9}$. -$10^{9}$ ≤ $Y_{i}$ ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 선수의 수 N이 주어진다. 이어지는 N개의 줄에는 선수들의 초기 좌표가 주어진다. 이 줄들 중 i번째 줄에는 두 정수 $X_{i}$와 $Y_{i}$가 주어지며, 이는 i번째 선수의 초기 위치 (1 ≤ i ≤ N)를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 선수들이 완벽한 수평선을 만들기 위해 필요한 최소 총 이동 횟수이다.

첫 번째 테스트 케이스에서 여러 최적해 중 하나는 두 번째 선수가 왼쪽으로 두 칸, 아래로 세 칸 이동하여 점 (2, 1)으로 가면 얻을 수 있다.

두 번째 테스트 케이스에서는 첫 번째 선수가 점 (0, 2)으로 이동하고 세 번째 선수가 점 (2, 2)으로 이동하면 총 네 번의 이동으로 완벽한 선을 만들 수 있다.