Rooks

A chessboard has $N$ rows and $N$ columns, and $N$ rooks stand on it. Two rooks attack each other when they share a cell, share a row, or share a column, so several rooks may start stacked on one cell.

One move shifts a single rook one cell up, down, left, or right. Diagonal moves are not allowed.

Move the $N$ rooks onto $N$ different cells so that no two of them attack each other. Report the smallest number of moves that is enough.

The first line contains the number of test cases $T$.

Each test case begins with a line containing $N$. Each of the next $N$ lines contains two integers, the row and the column of one rook, and both values are between $1$ and $N$ inclusive. $N$ is at most $20000$.

For each test case, print one line in the format Case #x: M, where $x$ is the test case number starting from $1$ and $M$ is the minimum number of moves needed to relocate the rooks.