题目描述

我们正在设计一种有点另类的排序算法，用于对包含 $1$ 到 $N$ 所有整数的数组 $A$ 进行排序。$A$ 中的整数最初可以是任意顺序。除了输入顺序外，该算法还依赖于两个整数 $P$（$P$ 不超过 $3$）和 $K$。算法的执行过程如下：

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$，使得通过合理选择分区和交换，可以将原始顺序排序。你能帮助我们计算出这个 $K$ 吗？

输入格式

输入的第一行给出测试用例的数量 $T$。

接下来有 $T$ 个测试用例。每个测试用例由两行组成。第一行包含两个整数 $N$ 和 $P$，含义如上所述。

测试用例的第二行包含 $N$ 个整数 $X_1, X_2, \dots, X_N$，表示数组 $A$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是参数 $K$ 的最大可能值。

5
5 2
1 5 4 3 2
5 2
4 5 1 2 3
6 2
6 3 5 2 4 1
5 3
4 5 1 2 3
6 3
1 2 6 4 5 3

Case #1: 4
Case #2: 2
Case #3: 3
Case #4: 3
Case #5: 6

提示

样例 #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]$

注意：前 $3$ 个样例不会出现在大数据集中，后 $2$ 个样例不会出现在小数据集中。

限制条件

$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$。

小数据集（测试集 1 – 可见）

$P = 2$。

大数据集（测试集 2 – 隐藏）

$P = 3$。

翻译由 DeepSeek V4 Pro 完成