룩 배치

$N$행 $N$열 체스판에 룩 $N$개가 놓여 있다. 두 룩이 같은 칸에 있거나, 같은 행에 있거나, 같은 열에 있으면 서로 공격한다. 그래서 처음에는 여러 룩이 한 칸에 겹쳐 있을 수도 있다.

한 번의 이동으로 룩 하나를 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 한 칸 옮길 수 있다. 대각선으로는 옮길 수 없다.

어떤 두 룩도 서로 공격하지 않도록 룩 $N$개를 서로 다른 칸 $N$개로 옮기려고 한다. 필요한 이동 횟수의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 $N$이 주어진다. 이어지는 $N$개의 줄에는 룩 하나의 행과 열을 나타내는 정수 두 개가 주어지고, 두 값은 모두 $1$ 이상 $N$ 이하이다. $N$은 최대 $20000$이다.

각 테스트 케이스마다 Case #x: M 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $M$은 룩을 옮기는 데 필요한 최소 이동 횟수이다.