자물쇠 열기

처음에 임의의 조합으로 설정된 $\mathbf{N}$개의 다이얼로 이루어진 번호 자물쇠가 있다고 생각해 보자. 자물쇠 다이얼의 크기는 $\mathbf{D}$이며, 이는 다이얼이 $0$ 이상 $\mathbf{D}-1$ 이하의 값을 가질 수 있고 위쪽이나 아래쪽으로 회전할 수 있다는 뜻이다. 또한 다이얼은 왼쪽에서 오른쪽 순서로 배치되며, 가장 왼쪽과 가장 오른쪽 다이얼의 위치는 각각 $1$와 $\mathbf{N}$이다. 모든 다이얼의 값을 $0$로 설정하면 자물쇠를 열 수 있다.

다음과 같은 연산을 없거나 그 이상 수행할 수 있다.

• $1 \le l \le r \le \mathbf{N}$를 만족하는 임의의 구간 $[l, r]$을 선택하고, $[l, r]$에 있는 모든 다이얼을 함께 위쪽이나 아래쪽으로 회전한다. 위쪽으로 회전하면 구간 $[l, r]$에 있는 각 다이얼의 값이 $1$만큼 증가하고, 아래쪽으로 회전하면 그 값이 $1$만큼 감소한다. 값이 $\mathbf{D}-1$인 다이얼은 증가할 때(위쪽으로 회전할 때) $0$가 되고, 값이 $0$인 다이얼은 감소할 때(아래쪽으로 회전할 때) $\mathbf{D}-1$가 된다는 점에 유의하라.

연산의 나열은 다음 조건을 만족해야 한다.

• $(i-1)$-번째 연산에서 선택한 구간 $[l_{i-1}, r_{i-1}]$은 $i$-번째 연산에서 선택한 구간 $[l_i, r_i]$에 완전히 포함되어야 한다. 즉, $l_i \le l_{i-1} \le r_{i-1} \le r_i$이어야 한다. 최초 구간($[l_1, r_1]$)은 임의로 선택할 수 있다.

초기 조합이 $[1, 1, 2, 2, 3, 3]$인 자물쇠를 여는 유효한 연산 순서의 예는 다음과 같다.

• 구간 $[5, 6]$을 아래쪽으로 회전한다.

• 구간 $[3, 6]$을 아래쪽으로 회전한다.

• 구간 $[1, 6]$을 아래쪽으로 회전한다.

다음은 수행할 수 없는 몇 가지 연산이다.

• $[6, 9]$ 이후에 구간 $[1, 4]$을 회전하는 것. $[6, 9]$가 $[1, 4]$에 완전히 포함되지 않기 때문이다($r_{i-1} = 9$와 $r_i = 4$일 때 $r_{i-1} \le r_{i}$를 만족하지 않는다).

• $[2, 7]$ 이후에 구간 $[3, 6]$을 회전하는 것.

목표는 자물쇠의 모든 다이얼을 $0$로 설정하는 데 필요한 유효한 연산의 최소 횟수를 출력하는 것이다.

제한

시간 제한: 30초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $0 \le \mathbf{V_i} \le \mathbf{D}-1$.

테스트 세트 1

$1 \le \mathbf{N} \le 40$. $\mathbf{D} = 2$.

테스트 세트 2

$1 \le \mathbf{N} \le 40$. $2 \le \mathbf{D} \le 10$.

테스트 세트 3

$1 \le \mathbf{N} \le 400$. $2 \le \mathbf{D} \le 10^9$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$와 $\mathbf{D}$가 주어지며, 각각 자물쇠의 다이얼 수와 다이얼의 크기를 나타낸다.

각 테스트 케이스의 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{V_1}, \mathbf{V_2}, \dots, \mathbf{V_N}$가 주어지며, $i$-번째 정수는 자물쇠 초기 조합의 $i$-번째 다이얼 값을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 문제 설명에 제시된 방식으로 자물쇠를 여는 데 필요한 최소 연산 횟수이다.

샘플 케이스 #1에서 자물쇠를 여는 데 필요한 최소 연산 횟수는 $3$이다. 다음 연산을 사용하여 자물쇠를 열 수 있다.

• 구간 $[4, 4]$을 아래쪽으로 회전한다.

• 구간 $[3, 5]$을 아래쪽으로 회전한다.

• 구간 $[1, 6]$을 아래쪽으로 회전한다.

샘플 케이스 #2에서 자물쇠를 여는 데 필요한 최소 연산 횟수는 $2$이다. 다음 연산을 사용하여 자물쇠를 열 수 있다.

• 구간 $[3, 4]$을 위쪽으로 회전한다.

• 구간 $[2, 6]$을 아래쪽으로 회전한다.

추가 샘플 - 테스트 세트 2

샘플 케이스 #1에서 자물쇠를 여는 데 필요한 최소 연산 횟수는 $3$이다. 다음 연산을 사용하여 자물쇠를 열 수 있다.

• 구간 $[5, 6]$을 아래쪽으로 회전한다.

• 구간 $[3, 6]$을 아래쪽으로 회전한다.

• 구간 $[1, 6]$을 아래쪽으로 회전한다.

샘플 케이스 #2에서 자물쇠를 여는 데 필요한 최소 연산 횟수는 $3$이다. 다음 연산을 사용하여 자물쇠를 열 수 있다.

• 구간 $[3, 4]$을 위쪽으로 회전한다.

• 구간 $[3, 4]$을 위쪽으로 회전한다.

• 구간 $[1, 6]$을 아래쪽으로 회전한다.