Manhattan Sort

You are given a sequence $S$ of $N$ distinct integers. Sort it into ascending order at the lowest possible cost, using only one operation.

The Manhattan swap: it takes the elements $S_i$ and $S_j$ sitting at positions $i$ and $j$, exchanges them, and costs $|i-j|$.

For example, the sequence $\{9, 5, 3\}$ becomes sorted after a single Manhattan swap. Exchange the first element with the last one and pay $2$, the distance between their positions.

The first line contains an integer $T$, the number of test cases. Each test case consists of two lines. The first line contains one integer $N$ ($1 \le N \le 30$), the length of the sequence $S$. The second line contains the $N$ elements of $S$, separated by spaces. All elements are distinct and fit in a 32 bit signed integer.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum cost of sorting the sequence into ascending order using only Manhattan swaps.