题目描述

我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。但是现在画布已经不再空白，因为画布上已经有了当下的风景。

我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1, k]$ 范围内的正整数表示。坦尼尔还要画他已经翻了的茶杯。每一次作画，他可以选定画布上的任意一个位置，然后将这个位置上的颜色涂改成 $[1, k]$ 范围内的任意正整数。

最后，我们都知道这幅画是有记忆的。定义画上留下的记忆碎片数量为画上的相同颜色连续块个数。现在坦尼尔想知道，如果给定他作画的次数上限为 $m$，那么画上的记忆碎片个数最多有多少。

输入格式

多组测试数据。

第一行输入一个正整数 $T$ 表示数据组数。

对于每组测试数据：

第一行输入三个正整数 $n, m, k$，表示画布的长度，坦尼尔作画的次数上限和颜色的取值范围。

第二行输入一个长度为 $n$ 的整数序列 $c_1, c_2, \dots, c_n$，表示画布上每个位置的初始颜色。

输出格式

对于每组测试数据，输出一行一个正整数，表示记忆碎片最多有多少个。

样例

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

3
5

样例解释

对于第一组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，得到序列 $[2, 1, 2]$，块数为 $3$。

对于第二组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，将从左到右的第三个位置涂成颜色 $3$，得到序列 $[2, 1, 3, 2, 3]$，块数为 $5$。

数据范围与提示

• $1 \le n \le 5 \times 10^5$，$\sum n \le 5 \times 10^5$
• $1 \le m \le n$
• $3 \le k \le 5 \times 10^5$
• $1 \le c_i \le k$

来源

CSPJ-重点算法班