题目描述

我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。

但是现在画布已经不再空白，因为画布上已经有了当下的风景。我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1,k]$ 范围内的正整数表示。

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

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

形式化题面

你有连续的 $n$ 个方格，每个方格上有一个初始颜色 $c_i$，且保证 $1\le c_i \le k$。

你可以操作至多 $m$ 次，每个操作为改变某个方格颜色，要求改变后的颜色范围仍在 $[1,k]$ 内。

我们称一个极长相同颜色连续段为一块，要求求出经过至多 $m$ 次操作后的最多块数。

输入格式

本题有多组测试数据。

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

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

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

输出格式

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

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

3
5

提示

样例解释

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

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

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据满足 $1\le n\le 5\times 10^5$，$1\le \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$。