问题描述

小蓝是一位有名的漆匠，他的朋友小桥有一个漆房，里面有一条长长的走廊，走廊两旁有许多相邻的房子，每间房子最初被涂上了一种颜色。

小桥来找小蓝，想让他把整个走廊都涂成同一个颜色。小蓝告诉小桥，他每天只能涂一段长度为 $k$ 的区间。对于每个区间，他可以选择将其中的房子重新涂上任何一种颜色，或者保持原来的颜色不变。

小桥想知道小蓝至少要涂几天，才能让整个走廊变成同一种颜色。

请帮助小桥解决这个问题。

输入格式

第一行包含一个整数 $t$（$1\le t\le 100$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1\le k\le n\le 10^4$），第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 60$），分别表示每个房子最初的颜色。

保证所有测试用例中 $n$ 的总和不超过 $10^4$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示小蓝需要涂漆的最少天数（即最少需要选取多少个长度为 $k$ 的区间，经过这些操作后能使整个走廊颜色一致）。

样例输入

2
5 2
1 1 2 2 1
6 2
1 2 2 3 3 3

样例输出

1
2