夏天,维卡喜欢参观她的乡间别墅。这里有放松的一切:舒适的秋千、自行车和河流。
河上有一座木桥,由 $$$n$$$ 木板组成。它很旧而且没有吸引力,所以维卡决定把它粉刷一下。在棚子里,他们刚刚发现了几罐$$$k$$$颜色的油漆。
在给每块木板涂上 $$$k$$$ 颜色之一后,维卡正准备去荡秋千,休息一下。然而她发现房子在河对岸,油漆还没有完全干,所以她还不能在桥上行走。
为了不破坏桥的外观,维卡决定仍然在桥上行走,但只踩相同颜色的木板。否则,她鞋底上的一小层油漆就会破坏另一种颜色的木板。维卡还剩下一点油漆,但只够重新粉刷桥的一块木板。
现在维卡站在第一块木板前面的地上。为了过桥,她会选择一些相同颜色的木板(重新粉刷后),其编号为 $$$1 \le i_1 < i_2 < \ldots < i_m \le n$$$ (木板从左到右编号为 $$$1$$$)。然后,由于 $$$m + 1$$$ 步中的每一步,维卡将必须穿过 $$$i_1 - 1, i_2 - i_1 - 1, i_3 - i_2 - 1, \ldots, i_m - i_{m-1} - 1, n - i_m$$$ 木板。
由于维卡害怕摔倒,所以她不想迈太远的步子。如果她能在过桥时将一块(或零块)木板重新涂上不同的颜色,请帮助她并告诉她一步中必须穿过的木板的最大数量。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 桥中木板的数量和不同颜色油漆的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le k$$$) — Vika 绘制桥板的颜色。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - Vika 在一步中必须跨过的木板的最小可能最大数量。
示例
输入 #1
5 5 2 1 1 2 1 1 7 3 1 2 3 3 3 2 1 6 6 1 2 3 4 5 6 8 4 1 2 3 4 2 3 1 4 3 1 1 1 1
输出 #1
0 1 2 2 0
注意
在第一个测试用例中,Vika 可以将中间的木板重新涂成 $$$1$$$ 颜色,并在不跨过任何木板的情况下走过桥。
在第二个测试用例中,Vika 可以将中间的木板重新涂成 $$$2$$$ 颜色,然后走过桥,每次只跨过一块木板。
在第三个测试用例中,Vika 可以将倒数第二块木板重新涂成 $$$2$$$ 颜色,然后走过桥,只踩在数字为 $$$2$$$ 和 $$$5$$$ 的木板上。那么 Vika 每次迈步时都必须跨过 $$$1$$$、$$$2$$$ 和 $$$1$$$ 木板,所以答案是 $$$2$$$。
在第四个测试用例中,Vika 可以简单地走过桥而无需重新粉刷,每次跨过两块木板,在颜色 $$$3$$$ 的木板上行走。
在第五个测试用例中,Vika 可以简单地走过桥,无需重新粉刷,也无需跨过任何木板。