Description

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

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

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

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

Input Format

多组测试数据。

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

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

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

对于 100% 的数据满足 1≤n≤5×105，1≤∑n≤5×105，1≤m≤n，3≤k≤5×105，1≤ci≤k。

Output Format

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

3
5

Hint

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

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

Source