Problems
Manhattan Sort
Manhattan Sort
Yet another sorting problem! In this one, you’re given a sequence \textbf{S} of \textbf{N} distinct integers and are asked to sort it with minimum cost using only one operation:
\textit{The Manhattan swap!}
Let \textbf{S_i} and \textbf{S_j} be two elements of the sequence at positions \textbf{i} and \textbf{j} respectively, applying the Manhattan swap operation to \textbf{S_i} and \textbf{S_j} swaps both elements with a cost of |\textbf{i-j}|. For example, given the sequence \{\textbf{9}, \textbf{5}, \textbf{3}\}, we can sort the sequence with a single Manhattan swap operation by swapping the first and last elements for a total cost of \textbf{2} (absolute difference between positions of \textbf{9} and \textbf{3}).
\InputFile
The first line of input contains an integer \textbf{T}, the number of test cases. Each test case consists of \textbf{2} lines. The first line consists of a single integer (\textbf{1} ≤ \textbf{N} ≤ \textbf{30}), the length of the sequence \textbf{S}. The second line contains \textbf{N} space separated integers representing the elements of \textbf{S}. All sequence elements are distinct and fit in \textbf{32} bit signed integer.
\OutputFile
For each test case, output one line containing a single integer, the minimum cost of sorting the sequence using only the Manhattan swap operation.
Input example #1
2 3 9 5 3 6 6 5 4 3 2 1
Output example #1
Case #1: 2 Case #2: 9