有一条街道,有 $$$n$$$ 房屋排成一排,编号从 $$$1$$$ 到 $$$n$$$。房子 $$$i$$$ 最初漆成颜色 $$$c_i$$$。如果所有的房子都漆成同样的颜色,这条街就被认为是美丽的。画家汤姆负责把街道变得美丽。汤姆的绘画能力由一个整数定义,我们称之为$$$k$$$。
有一天,Tom 可以执行以下重新绘制过程,该过程包含两个步骤:
1. 他选择两个整数 $$$l$$$ 和 $$$r$$$ 使得 $$$ 1 \le l \le r \le n $$$ 和 $$$ r - l + 1 = k $$$。
2. 对于每个房子$$$i$$$,使得$$$l \le i \le r$$$,他可以用他想要的任何颜色重新粉刷它,或者忽略它并让它保持当前的颜色。
请注意,汤姆在同一天可以使用不同的颜色重新粉刷不同的房子。
汤姆想知道重新粉刷街道使其变得美丽所需的最少天数。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$ 1 \le t \le 10^4$$$),即测试用例的数量。测试用例的描述如下。
在测试用例描述的第一行中有两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^5$$$)。
第二行包含 $$$n$$$ 空格分隔的整数。这些整数中的第 $$$i$$$ 代表 $$$c_i$$$ ($$$1 \le c_i \le 100$$$),即房子 $$$i$$$ 最初绘制的颜色。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
打印 $$$t$$$ 行,每行有一个整数:对于每个测试用例,Tom 需要使街道变得美丽的最小天数。
示例
输入 #1
3 10 2 1 1 2 2 1 1 2 2 2 1 7 1 1 2 3 4 5 6 7 10 3 1 3 3 3 3 1 2 1 3 3
输出 #1
3 6 2
注意
在第一个测试用例中,Tom 应在第一天将房屋 1 和 2 涂成颜色 2,在第二天将房屋 5 和 6 涂成颜色 2,并在第三天将最后一个房子涂成颜色 2。
例如,在第二个测试用例中,汤姆可以花 6 天的时间将房屋 1、2、4、5、6、7 涂成颜色 3。
在第三个测试用例中,Tom 可以在第一天用颜色 3 绘制第一栋房子,并在第二天用颜色 3 绘制房屋 6、7 和 8。