Airport Sort

A few airlines do not assign seat numbers before boarding. Every passenger gets one ticket instead, and the ticket carries a distinct integer in $[1, n]$, where $n$ is the number of seats on the plane. Ticket numbers are grouped into zones. One zone holds $k$ tickets, so numbers $1$ through $k$ are zone 1, numbers $k+1$ through $2k$ are zone 2, and the pattern continues. If $n$ is not divisible by $k$, the last zone holds fewer than $k$ tickets.

Before boarding, the $n$ passengers line up in an arbitrary order. Boarding finishes sooner when the first $k$ passengers in the line hold zone 1 tickets, the next $k$ hold zone 2 tickets, and so on. The order inside a zone does not matter. There are two ways to rearrange the line.

1. Two neighbours swap places. Only one adjacent pair can swap per second, and the swapping repeats until the line reaches the required order.
2. All passengers walk to their own positions at the same time. Walking from position $x$ to position $y$ takes $|x - y|$ seconds. Everybody moves at once, so the line takes as long as the passenger who walks the longest.

The first approach takes more time, but it is less noisy. Your task is to measure how much faster the second one is. Let $X$ be the minimum time of the first approach and $Y$ the minimum time of the second approach, then compute $X - Y$.

Suppose $n = 10$, $k = 3$, and the line reads 3 7 1 2 4 6 5 8 10 9 from the front. Each integer is the ticket number of the passenger standing there, so the passenger at the front holds ticket 3. The passengers holding tickets 7, 2, 5, 10 and 9 are not in their right positions.

The first approach needs at least 6 swaps, which is 6 seconds.

1. swap 7 with 1, giving 3 1 7 2 4 6 5 8 10 9
2. swap 7 with 2, giving 3 1 2 7 4 6 5 8 10 9
3. swap 7 with 4, giving 3 1 2 4 7 6 5 8 10 9
4. swap 7 with 6, giving 3 1 2 4 6 7 5 8 10 9
5. swap 7 with 5, giving 3 1 2 4 6 5 7 8 10 9
6. swap 10 with 9, giving 3 1 2 4 6 5 7 8 9 10, and now everyone stands where they belong.

The second approach takes 5 seconds if the final order is 3 2 1 4 6 5 7 8 9 10. The passengers holding tickets 3, 1 and 8 already stand in the right place, the passengers holding tickets 4, 5, 6, 9 and 10 walk for 1 second, the passenger holding ticket 2 walks for 2 seconds, and the passenger holding ticket 7 walks for 5 seconds. Other final orders also take 5 seconds, and nothing under 5 seconds is possible. So $X = 6$, $Y = 5$, and the second approach is 1 second faster.

The first line holds the number of test cases $T$. ($T < 50$)

Each test case takes two lines. The first line holds the positive integers $n$ and $k$. ($n \le 20000$, $k \le n$) The second line holds $n$ distinct integers in $[1, n]$. The first integer is the ticket number of the passenger standing at the front of the line.

For each test case, print one line in the form Case x: y, where $x$ is the test case number starting at 1 and $y$ is how many seconds faster the second approach is, that is $X - Y$.