{"raw_statement":[{"iden":"statement","content":"我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。\n\n但是现在画布已经不再空白，因为画布上已经有了当下的风景。我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1,k]$ 范围内的正整数表示。\n\n坦尼尔还要画他已经翻了的茶杯。每一次作画，他可以选定画布上的任意一个位置，然后将这个位置上的颜色涂改成 $[1,k]$ 范围内的任意正整数。\n\n最后，我们都知道这幅画是有记忆的。定义画上留下的记忆碎片数量为画上的**相同颜色连续块个数**。现在坦尼尔想知道，如果给定他作画的次数**上限**，那么画上的记忆碎片个数**最多**有多少。\n\n**形式化题面**\n\n你有连续的 $n$ 个方格，每个方格上有一个初始颜色 $c_i$，且保证 $1\\le c_i \\le k$。\n\n你可以操作**至多** $m$ 次，每个操作为改变某个方格颜色，要求改变后的颜色范围仍在 $[1,k]$ 内。\n\n我们称一个**极长相同颜色连续段**为一块，要求求出经过至多 $m$ 次操作后的**最多**块数。\n"},{"iden":"input","content":"本题有多组测试数据。\n\n第一行输入一个正整数 $T$ 表示数据组数。\n\n对于每组测试数据，第一行输入三个正整数 $n,m,k$，表示画布的长度，坦尼尔作画的次数上限和颜色的取值范围。\n\n第二行输入一个长度为 $n$ 的整数序列 $c$，表示画布上每个位置的初始颜色。"},{"iden":"output","content":"对于每组测试数据，输出一行一个正整数，表示记忆碎片最多有多少个。"},{"iden":"note","content":"**样例解释**\n\n对于第一组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，得到 $\\{c_n\\}=\\{2,1,2\\}$，块数为 $3$。\n\n\n对于第二组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，将从左到右的第三个位置涂成颜色 $3$，得到 $\\{c_n\\}=\\{2,1,3,2,3\\}$，块数为 $5$。\n\n**数据范围**\n\n**本题采用捆绑测试**。\n\n| $\\text{Subtask}$ | $\\sum n\\le$ | $m\\le$ | $k\\le$ | 分值 |\n| :-----------: | :-----------: | :-----------: | :-----------: | :-----------:  |\n| $1$ | $10$ | $10$ | $3$ | $10$ |\n| $2$ | $5\\times 10^5$ | $1$ | $5\\times 10^5$ | $10$ |\n| $3$ | $10^3$ | $10^3$ | $10^3$ | $15$ |\n| $4$ | $5\\times 10^5$ | $5\\times 10^5$ | $3$ | $25$ |\n| $5$ | $5\\times 10^5$ | $5\\times 10^5$ | $5\\times 10^5$ | $40$ |\n\n对于 $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$。\n"}],"translated_statement":null,"sample_group":[["2\n3 1 3\n2 2 2\n5 2 4\n2 2 2 2 3","3\n5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}