럭비

어떤 먼 행성에서는 무한한 2차원 직교 좌표계 위에서 럭비를 한다. 선수는 정수 격자점만 차지할 수 있고, 한 번에 동서남북 네 방향 중 하나로 이웃한 격자점으로 이동할 수 있다. 즉 선수가 현재 점 (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)를 차지하도록 이동해야 한다. 선수들이 일직선의 위치를 좌표계 안에서 마음대로 정할 수 있고 선수의 순서는 중요하지 않다면, 완벽한 일직선을 만들기 위해 선수들이 해야 하는 걸음 수의 합의 최솟값은 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 따른다. 각 테스트 케이스의 첫 줄에는 선수의 수 N이 주어진다. 그다음 N개의 줄에 선수들의 처음 좌표가 주어진다. 이 줄들 중 i번째 줄에는 두 정수 Xi와 Yi가 있으며, 이는 i번째 선수의 처음 위치를 나타낸다 (1 ≤ i ≤ N).

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 선수들이 완벽한 가로 일직선을 만들기 위해 해야 하는 걸음 수의 합의 최솟값이다.

• 1 ≤ T ≤ 100.

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

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