시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB58312764.286%

문제

Yet another sorting problem! In this one, you’re given a sequence S of N distinct integers and are asked to sort it with minimum cost using only one operation: 

The Manhattan swap! 

Let Si and Sj be two elements of the sequence at positions i and j respectively, applying the Manhattan swap operation to Si and Sj swaps both elements with a cost of |i-j|. For example, given the sequence {9,5,3}, we can sort the sequence with a single Manhattan swap operation by swapping the first and last elements for a total cost of 2 (absolute difference between positions of 9 and 3). 

입력

The first line of input contains an integer T, the number of test cases. Each test case consists of 2 lines. The first line consists of a single integer (1 <= N <= 30), the length of the sequence S. The second line contains N space separated integers representing the elements of S. All sequence elements are distinct and fit in 32 bit signed integer.

출력

For each test case, output one line containing a single integer, the minimum cost of sorting the sequence using only the Manhattan swap operation. 

예제 입력 1

2
3
9 5 3
6
6 5 4 3 2 1

예제 출력 1

Case #1: 2
Case #2: 9