평탄화

Blotch는 벽을 만들었다. 벽은 N개의 구간으로 이루어져 있으며, 왼쪽에서 오른쪽으로 1부터 N까지 번호가 매겨져 있다. 그는 서둘러 벽을 만들었기 때문에 모든 구간의 높이가 같지는 않다. 벽의 i번째 구간의 높이는 $A_{i}$미터이다.

Blotch는 일부 구간을 다시 만들어 벽을 고치려고 한다. Blotch는 다시 만드는 각 구간의 높이를 자신이 선택한 임의의 높이로 설정할 수 있다.

$A_{i}$ ≠ $A_{i+1}$인 인덱스 i (1 ≤ i < N)의 개수가 K 이하이면 Blotch는 만족한다.

Blotch가 만족하려면 벽의 구간을 최소 몇 개 다시 만들어야 하는가?

제한

시간 제한: 테스트 세트당 TBD초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해, 1 ≤ $A_{i}$ ≤ 1000. 0 ≤ K ≤ N.

테스트 세트 1 (공개)

2 ≤ N ≤ 20.

테스트 세트 2 (비공개)

2 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 벽 구간의 수와 인접한 구간 사이에서 높이가 변하는 횟수의 최댓값을 각각 나타내는 두 정수 N과 K가 포함된 한 줄로 시작한다.

두 번째 줄에는 N개의 정수가 주어진다. i번째 정수는 벽의 i번째 구간의 높이인 $A_{i}$이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 Blotch가 만족하기 위해 다시 만들어야 하는 구간의 최소 개수이다.

첫 번째 예제 케이스에서 벽은 N = 8개의 구간으로 이루어져 있으며, 인접한 구간 사이에서 높이가 변하는 횟수가 최대 K = 2번이면 Blotch는 만족한다. Blotch는 다음과 같이 할 수 있다.

• 벽의 2nd 구간을 높이 300이 되도록 다시 만들고,

• 벽의 6th 구간을 높이 200이 되도록 다시 만들고,

• 벽의 8th 구간을 높이 800이 되도록 다시 만든다.

그러면 각 구간의 높이가 300, 300, 300, 300, 200, 200, 800, 800인 벽이 만들어지며, Blotch는 만족한다.

두 번째 예제 케이스에서 벽은 N = 5개의 구간으로 이루어져 있으며, 인접한 구간 사이에서 높이가 변하는 횟수가 최대 K = 3번이면 Blotch는 만족한다. Blotch는 이미 이 벽에 만족하므로 어떤 구간도 다시 만들 필요가 없다.

세 번째 예제 케이스에서 벽은 N = 7개의 구간으로 이루어져 있으며, 인접한 구간 사이에서 높이가 변하는 횟수가 최대 K = 3번이면 Blotch는 만족한다. Blotch는 다음과 같이 할 수 있다.

• 벽의 2nd 구간을 높이 10이 되도록 다시 만든다.

그러면 각 구간의 높이가 10, 10, 40, 10, 10, 30, 30인 벽이 만들어지며, Blotch는 만족한다.

네 번째 예제 케이스에서 벽은 N = 10개의 구간으로 이루어져 있으며, 인접한 구간 사이에서 높이가 변하는 횟수가 최대 K = 2번이면 Blotch는 만족한다. Blotch는 다음과 같이 할 수 있다.

• 벽의 5th 구간을 높이 60이 되도록 다시 만들고,

• 벽의 6th 구간을 높이 60이 되도록 다시 만든다.

그러면 각 구간의 높이가 30, 30, 60, 60, 60, 60, 60, 60, 30, 30인 벽이 만들어지며, Blotch는 만족한다.