CF1415B.Repainting Street

There is a street with $n$ houses in a line, numbered from $1$ to $n$. The house $i$ is initially painted in color $c_i$. The street is considered beautiful if all houses are painted in the same color. Tom, the painter, is in charge of making the street beautiful. Tom's painting capacity is defined by an integer, let's call it $k$.

On one day, Tom can do the following repainting process that consists of two steps:

1. He chooses two integers $l$ and $r$ such that $ 1 \le l \le r \le n $ and $ r - l + 1 = k $.
2. For each house $i$ such that $l \le i \le r$, he can either repaint it with any color he wants, or ignore it and let it keep its current color.

Note that in the same day Tom can use different colors to repaint different houses.

Tom wants to know the minimum number of days needed to repaint the street so that it becomes beautiful.

一条街道上有 $n$ 座房屋排成一行，编号从 $1$ 到 $n$。初始时，第 $i$ 座房屋被涂成颜色 $c_i$。当所有房屋都被涂成同一种颜色时，该街道被认为是“美丽的”。汤姆（Tom）是一名粉刷匠，负责将这条街道变得美丽。汤姆的粉刷能力由一个整数定义，我们称之为 $k$。

在一天之内，汤姆可以执行如下重涂操作，该操作包含两个步骤：

1. 他选择两个整数 $l$ 和 $r$，满足 $ 1 \le l \le r \le n $ 且 $ r - l + 1 = k $。
2. 对于每个满足 $l \le i \le r$ 的房屋 $i$，他可以选择将其重涂为任意颜色，也可以选择忽略它，使其保持当前颜色。

注意：在同一天内，汤姆可以对不同的房屋使用不同的颜色进行重涂。

汤姆想知道，使街道变得美丽所需的最少天数是多少？

The first line of input contains a single integer $t$ ($ 1 \le t \le 10^4$), the number of test cases. Description of test cases follows.

In the first line of a test case description there are two integers $n$ and $k$ ($1 \le k \le n \le 10^5$).

The second line contains $n$ space-separated integers. The $i$-th of these integers represents $c_i$ ($1 \le c_i \le 100$), the color which house $i$ is initially painted in.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $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$。

Print $t$ lines, each with one integer: the minimum number of days Tom needs to make the street beautiful for each test case.

输出 $t$ 行，每行一个整数：对于每个测试用例，Tom 使街道变得美观所需的最少天数。

In the first test case Tom should paint houses 1 and 2 in the first day in color 2, houses 5 and 6 in the second day in color 2, and the last house in color 2 on the third day.

In the second test case Tom can, for example, spend 6 days to paint houses 1, 2, 4, 5, 6, 7 in color 3.

In the third test case Tom can paint the first house in the first day and houses 6, 7, and 8 in the second day in color 3.

在第一个测试用例中，Tom 应在第一天将房屋 1 和 2 涂成颜色 2，第二天将房屋 5 和 6 涂成颜色 2，第三天将最后一栋房屋涂成颜色 2。

在第二个测试用例中，Tom 可以（例如）花费 6 天时间，将房屋 1、2、4、5、6、7 涂成颜色 3。

在第三个测试用例中，Tom 可以在第一天涂第一栋房屋，在第二天将房屋 6、7 和 8 涂成颜色 3。