배열 정렬하기 (스몰)

1부터 $N$까지의 정수가 한 번씩 들어 있는 배열 $A$를 정렬하는, 조금 색다른 알고리즘을 만들고 있다. $A$의 원소는 처음에 임의의 순서로 놓여 있다. 이 알고리즘은 입력 순서 말고도 두 정수 $P$와 $K$에 따라 달라진다. $P$는 3 이하이다. 동작 방식은 다음과 같다.

1. $A$를 비어 있지 않은 $K$개의 부분 배열 $A_1, A_2, \dots, A_K$로 나눈다. 이때 $A_1 A_2 \dots A_K$를 순서대로 이어 붙이면 다시 $A$가 되어야 한다.
2. 각 부분 배열을 따로 정렬한다.
3. 부분 배열 중 최대 $P$개를 고르고, 고른 것 중 두 개의 자리를 맞바꾸는 일을 원하는 횟수만큼 한다.

예를 들어 $A = [1\ 5\ 4\ 3\ 2]$이고 $P = 2$라고 하자. $K = 4$로 나누는 한 가지 방법은 다음과 같다.

A1 = [1]
A2 = [5]
A3 = [4]
A4 = [3 2]

각 부분 배열을 정렬한 뒤

A1 = [1]
A2 = [5]
A3 = [4]
A4 = [2 3]

A4와 A2의 자리를 맞바꾼 뒤

A1 = [1]
A2 = [2 3]
A3 = [4]
A4 = [5]

이 알고리즘이 분산 환경에 잘 맞는다는 것을 보이려고 한다. 입력과 $P$가 고정되었을 때, 분할과 교환을 잘 골라서 원래 배열을 정렬할 수 있는 $K$의 최댓값을 구하라.

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

이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에는 위에서 설명한 두 정수 $N$과 $P$가 주어진다. 둘째 줄에는 배열 $A$를 나타내는 $N$개의 정수 $X_1, X_2, \dots, X_N$이 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $K$가 가질 수 있는 최댓값이다.

• $1 \le T \le 100$
• $1 \le N \le 5000$
• 모든 $i$에 대해 $1 \le X_i \le N$
• $i \ne j$이면 $X_i \ne X_j$
• $P = 2$

예제 입력의 첫 번째 테스트 케이스는 문제에서 설명한 과정과 같다.

두 번째 테스트 케이스는 다음과 같이 나눈다.

[4 5] [1 2 3]
두 부분 배열의 자리를 맞바꾸면: [1 2 3] [4 5]

세 번째 테스트 케이스는 다음과 같이 나눈다.

[6] [3 5 2 4] [1]
[3 5 2 4]를 정렬한 뒤 [6]과 [1]의 자리를 맞바꾸면: [1] [2 3 4 5] [6]