배열 정렬하기 (Large)

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

1. $A$를 비어 있지 않은 연속 부분 배열 $K$개 $A_1, A_2, \ldots, A_K$로 나눈다. 이 부분 배열을 순서대로 이어 붙인 $A_1A_2 \ldots 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$가 주어질 때, 부분 배열 나누기와 맞바꾸기를 잘 골라서 $A$를 정렬할 수 있는 $K$의 최댓값을 구하라.

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

이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 두 정수 $N$과 $P$가 주어진다.

둘째 줄에는 배열 $A$를 나타내는 $N$개의 정수 $X_1, X_2, \ldots, X_N$이 주어진다.

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

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

1번 케이스: 문제 설명의 예시와 같다.

2번 케이스:

[4 5] [1 2 3]
두 부분 배열을 맞바꾸면: [1 2 3] [4 5]

3번 케이스:

[6] [3 5 2 4] [1]
[3 5 2 4]를 정렬하고 [6]과 [1]을 맞바꾸면: [1] [2 3 4 5] [6]

4번 케이스:

[4 5] [1] [2 3]
[4 5]와 [1]을 맞바꾸고 다시 [2 3]과 [4 5]를 맞바꾸면: [1] [2 3] [4 5]

5번 케이스:

[1] [2] [6] [4] [5] [3]
[6]과 [3]을 맞바꾸면: [1] [2] [3] [4] [5] [6]