공항 탑승 줄 정렬

좌석 번호를 미리 정하지 않는 항공사가 있다. 승객은 표를 한 장씩 받고, 표에는 $1$ 이상 $n$ 이하의 서로 다른 정수가 적혀 있다. $n$은 비행기의 좌석 수다. 표 번호는 구역으로 나뉜다. 한 구역에 표 $k$장이 들어가므로 번호 $1$부터 $k$까지가 1번 구역, $k+1$부터 $2k$까지가 2번 구역이고, 그다음도 같은 방식이다. $n$이 $k$로 나누어떨어지지 않으면 마지막 구역에는 표가 $k$장보다 적게 들어간다.

탑승 전에 승객 $n$명이 아무 순서로 한 줄로 선다. 탑승을 빨리 끝내려면 줄의 앞 $k$명이 1번 구역, 그다음 $k$명이 2번 구역, 이후도 같은 방식으로 서 있어야 한다. 같은 구역 안에서는 서는 순서가 상관없다. 줄을 이렇게 바꾸는 방법은 두 가지다.

1. 이웃한 두 승객이 자리를 바꾼다. 1초에 이웃한 한 쌍만 자리를 바꿀 수 있고, 원하는 순서가 될 때까지 교환을 반복한다.
2. 모든 승객이 동시에 자기 자리로 걸어간다. 위치 $x$에서 위치 $y$로 걸어가는 데 $|x - y|$초가 걸린다. 다 같이 움직이므로 걸리는 시간은 가장 오래 걷는 승객의 시간이다.

첫 번째 방법이 시간은 더 걸리지만 덜 시끄럽다. 두 번째 방법이 얼마나 빠른지 구하면 된다. 첫 번째 방법으로 줄을 정리하는 최소 시간을 $X$, 두 번째 방법의 최소 시간을 $Y$라고 할 때 $X - Y$를 구한다.

$n = 10$, $k = 3$이고 줄이 앞에서부터 3 7 1 2 4 6 5 8 10 9 순서라고 하자. 각 정수는 그 자리에 선 승객의 표 번호다. 맨 앞에 선 승객의 표는 3번이다. 표 번호가 7, 2, 5, 10, 9인 승객은 제자리에 없다.

첫 번째 방법으로는 교환을 최소 6번 해야 하므로 6초가 걸린다.

1. 7과 1을 교환하면 3 1 7 2 4 6 5 8 10 9
2. 7과 2를 교환하면 3 1 2 7 4 6 5 8 10 9
3. 7과 4를 교환하면 3 1 2 4 7 6 5 8 10 9
4. 7과 6을 교환하면 3 1 2 4 6 7 5 8 10 9
5. 7과 5를 교환하면 3 1 2 4 6 5 7 8 10 9
6. 10과 9를 교환하면 3 1 2 4 6 5 7 8 9 10이 되어 모두 제자리에 선다.

두 번째 방법으로는 최종 순서를 3 2 1 4 6 5 7 8 9 10으로 정하면 5초가 걸린다. 표 번호가 3, 1, 8인 승객은 이미 제자리에 있고, 표 번호가 4, 5, 6, 9, 10인 승객은 1초, 표 번호가 2인 승객은 2초, 표 번호가 7인 승객은 5초 걷는다. 5초가 나오는 최종 순서는 여러 가지지만 5초보다 줄일 수는 없다. 따라서 $X = 6$, $Y = 5$이고 두 번째 방법이 1초 빠르다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T < 50$)

각 테스트 케이스는 두 줄이다. 첫 줄에 양의 정수 $n$과 $k$가 주어진다. ($n \le 20000$, $k \le n$) 두 번째 줄에 $1$ 이상 $n$ 이하의 서로 다른 정수 $n$개가 주어진다. 첫 번째 정수는 줄의 맨 앞에 선 승객의 표 번호다.

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 두 번째 방법이 몇 초 더 빠른지, 즉 $X - Y$다.