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:

He chooses two integers $l$ and $r$ such that $ 1 \le l \le r \le n $ and $ r - l + 1 = k $.

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.


-----Input-----

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$.


-----Output-----

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


-----Examples-----

Input
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
Output
3
6
2


-----Note-----

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.

Difficulty: EASY
Tags: Complete search

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	if k == 1:
		print(n - max(Counter(w).values()))
	else:
		(d, m) = (set(w), 10 ** 5)
		for i in d:
			(a, b) = (0, 0)
			while a < n:
				if w[a] != i:
					a += k
					b += 1
				else:
					a += 1
			m = min(m, b)
		print(m)


def repaint(n, k, array):
	s = set(array)
	min_ans = n
	for x in s:
		l = 0
		r = k + l - 1
		ans = 0
		while l < n:
			if array[l] == x:
				l += 1
				r = k + l - 1
			else:
				ans += 1
				l = l + k
				r = k + l - 1
		if ans < min_ans:
			min_ans = ans
	return min_ans
t = int(input())
final = []
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	final.append(repaint(n, k, l))
for _ in range(t):
	print(final[_])


from sys import stdin, stdout
from collections import Counter
from itertools import permutations
import bisect
import math
I = lambda : map(int, stdin.readline().split())
I1 = lambda : stdin.readline()

def solve():
	(n, k) = I()
	c = list(I())
	s = list(set(c))
	ans = 1000005
	for x in s:
		cnt = 0
		i = 0
		while i < n:
			if c[i] != x:
				i += k
				cnt += 1
			else:
				i += 1
		ans = min(ans, cnt)
	print(ans)
T = int(I1())
for _ in range(T):
	solve()


def main():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		c = input().split()
		dic = dict()
		for c_i in c:
			if dic.get(c_i) is None:
				dic[c_i] = 1
			else:
				dic[c_i] += 1
		ans = []
		for color in dic.keys():
			temp = color
			cont = 0
			j = 0
			while j < n:
				if c[j] != temp:
					cont += 1
					j = j + k - 1
				j += 1
			ans.append(cont)
		print(min(ans))
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	s = set(c)
	ans = 10 ** 9
	for item in s:
		i = 0
		count = 0
		while i < n:
			if c[i] == item:
				i += 1
			else:
				i += k
				count += 1
		ans = min(ans, count)
	print(ans)


I = input
for _ in range(int(I())):
	(n, k) = map(int, I().split())
	lst = list(map(int, I().split()))
	ans = n
	for c in set(lst):
		(i, res) = (0, 0)
		while i < n:
			if lst[i] == c:
				i += 1
			else:
				i += k
				res += 1
		ans = min(res, ans)
	print(ans)


import sys

def ria():
	return list(map(int, sys.stdin.readline().split()))

def Madara(v, k, c):
	q = 0
	s = 0
	while q < len(v):
		if v[q] == c:
			q += 1
			continue
		q += k
		s += 1
	return s

def Holo():
	(_, k) = map(lambda x: int(x), input().split())
	v = ria()
	qm = 10000000000.0
	mc = max(v)
	for i in range(1, mc + 1):
		i = Madara(v, k, i)
		if i < qm:
			qm = i
	return qm
z = []
t = int(input())
for i in range(t):
	z.append(Holo())
print('\n'.join(list(map(lambda x: str(x), z))))


def fun(A, n, k):
	c = set(A)
	res = 10 ** 8
	for m in c:
		ans = 0
		i = 0
		while i < n:
			if A[i] != m:
				ans += 1
				i += k
			else:
				i += 1
		res = min(res, ans)
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	print(fun(A, n, k))


def solve_for_color(color, n, k, arr):
	(answer, head) = (0, 0)
	while head < n:
		while arr[head] == color:
			head += 1
			if head >= n:
				return answer
		(answer, head) = (answer + 1, head + k)
	return answer

def solve():
	(n, k) = map(int, input().split())
	house_paintings = list(map(int, input().split()))
	used_colors = set(house_paintings)
	return min(map(lambda c: solve_for_color(c, n, k, house_paintings), used_colors))
for _ in range(int(input())):
	print(solve())


import sys
import math
import random
from queue import PriorityQueue as PQ
from bisect import bisect_left as BSL
from bisect import bisect_right as BSR
from collections import OrderedDict as OD
from collections import Counter
from itertools import permutations
from decimal import Decimal as BIGFLOAT
mod = 1000000007
sys.setrecursionlimit(1000000)
try:
	sys.stdin = open('actext.txt', 'r')
	OPENFILE = 1
except:
	pass

def get_ints():
	return map(int, input().split())

def palindrome(s):
	mid = len(s) // 2
	for i in range(mid):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True

def check(i, n):
	if 0 <= i < n:
		return True
	else:
		return False

def brute(arr, n, k):
	colorset = set(arr)
	ans = n - 1
	count = 0
	temp = 0
	for cs in colorset:
		i = 0
		temp = 0
		while i < n:
			if arr[i] != cs:
				temp += 1
				i += k
			else:
				i += 1
		ans = min(temp, ans)
	return ans
t = int(input())
for tt in range(t):
	(n, k) = get_ints()
	arr = list(get_ints())
	print(brute(arr, n, k))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 100000
	s = set(a)
	for i in s:
		j = 0
		c = 0
		while j < n:
			if a[j] != i:
				c = c + 1
				j = j + k
			else:
				j = j + 1
		ans = min(ans, c)
	print(ans)


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = n
	a = list(set(l))
	for i in a:
		s = 0
		j = 0
		while j < n:
			if l[j] == i:
				j += 1
			else:
				j += k
				s += 1
		c = min(c, s)
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = [int(j) for j in input().split()]
	a = [int(j) for j in input().split()]
	cnt = n
	for c in set(a):
		cnt0 = 0
		i = 0
		while i < n:
			if a[i] == c:
				i += 1
			else:
				i += k
				cnt0 += 1
		cnt = min(cnt, cnt0)
	print(cnt)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	set1 = set(arr)
	ans = 1e+19
	for i in set1:
		temp = 0
		j = 0
		while j < n:
			if arr[j] != i:
				temp += 1
				j += k
			else:
				j += 1
		ans = min(ans, temp)
	print(ans)


from sys import stdin, stdout
import math
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	maxq = 0
	col = {}
	di = {}
	for i in arr:
		if i in di:
			di[i] += 1
		else:
			di[i] = 1
	mindays = 10 ** 9
	for i in di:
		start = 0
		end = 0
		days = 0
		j = 0
		while j < n:
			if arr[j] == i:
				while j < n and arr[j] == i:
					j += 1
			else:
				j += k
				days += 1
		mindays = min(mindays, days)
	print(mindays)


def solution(n, k, clist):
	total_day = 10 ** 5
	color_candi = set()
	for i in clist:
		if i not in color_candi:
			color_candi.add(i)
	for cur_color in color_candi:
		i = 0
		cnt = 0
		while i < len(clist):
			if clist[i] == cur_color:
				i += 1
			else:
				i += k
				cnt += 1
		if cnt < total_day:
			total_day = cnt
	return total_day
t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	clist = list(map(int, input().split()))
	print(solution(n, k, clist))


t = int(input())
d = []
for i in range(t):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	s = set(a)
	cc = float('+inf')
	for q in s:
		j = 0
		c = 0
		while j < n:
			if a[j] != q:
				c += 1
				j += k
			else:
				j += 1
		cc = min(cc, c)
	d.append(cc)
for i in d:
	print(i)


import sys

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math
from collections import defaultdict
for _ in range(ri()):
	(n, k) = ria()
	l = ria()
	y = set(l)
	ans = []
	for x in y:
		i = 0
		cnt = 0
		while i < n:
			if l[i] != x:
				cnt += 1
				i += k
			else:
				i += 1
		ans.append(cnt)
	print(min(ans))


import sys
for _ in range(int(input())):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	l = [int(i) for i in input().split()]
	mini = sys.maxsize
	for ans in set(l):
		i = 0
		day = 0
		while i < len(l):
			if l[i] != ans:
				day += 1
				i += k
			else:
				i += 1
		if mini > day:
			mini = day
	print(mini)


n = int(input())
for _ in range(n):
	(n, k) = map(int, input().split())
	colors = list(map(int, input().split()))
	days = 100000
	for color in set(colors):
		i = 0
		d = 0
		while i < n:
			if color != colors[i]:
				d += 1
				i += k
			else:
				i += 1
		if d < days:
			days = d
	print(days)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	unq = set(c)
	ans = float('inf')
	for val in unq:
		i = 0
		days = 0
		while i < n:
			if c[i] != val:
				days += 1
				i += k
				continue
			i += 1
		ans = min(ans, days)
	print(ans)


def solve():
	(num_houses, limit) = [int(a) for a in input().split()]
	houses = list(map(int, input().split()))
	colors = set(houses)
	days_req = num_houses
	for c in colors:
		index = 0
		curr_days = 0
		while True:
			if index >= num_houses:
				break
			if houses[index] == c:
				index += 1
			else:
				index += limit
				curr_days += 1
		days_req = min(curr_days, days_req)
	print(days_req)
num_t = int(input())
for _ in range(num_t):
	solve()


import sys
from collections import Counter
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = Counter(a).most_common()
	ln = len(c)
	if k >= n - 1 and len(c) != 1:
		print(1)
	else:
		cntmn = 10000000000.0
		for j in range(min(ln, n // 2 + 1)):
			d = c[j][0]
			cnt = i = 0
			while i < n:
				if a[i] != d:
					cnt += 1
					i += k
				else:
					i += 1
			cntmn = min(cntmn, cnt)
		print(cntmn)


def getnums():
	return map(int, input().split())

def solve(n, k, c, x):
	i = 0
	d = 0
	while i < n:
		if c[i] != x:
			d += 1
			i += k
		else:
			i += 1
	return d
(t,) = getnums()
for i in range(t):
	(n, k) = getnums()
	c = list(getnums())
	nums = set(c)
	dmin = n
	for x in nums:
		d = solve(n, k, c, x)
		if d < dmin:
			dmin = d
	print(dmin)


from math import ceil

def solve(arr, n, k):
	a = set(arr)
	day = 100000001
	for i in a:
		ans = 0
		x = 0
		while x < n:
			if i != arr[x]:
				x += k
				ans += 1
			else:
				x += 1
		day = min(ans, day)
	return day
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solve(arr, n, k))


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
for _ in range(t()):
	(n, k) = ll()
	a = list(ll())
	d = list(set(a))
	ans = 10000000
	for mx in d:
		c = 0
		i = 0
		while i < n:
			if a[i] != mx:
				c += 1
				i += k
			else:
				i += 1
		ans = min(ans, c)
	print(ans)


import math

def check(arr, x, k):
	i = 0
	ans = 0
	while i < len(arr):
		if arr[i] == x:
			i += 1
		else:
			i += k
			ans += 1
	return ans

def proB(arr, k):
	ans = math.inf
	for i in range(1, max(arr) + 1):
		ans = min(ans, check(arr, i, k))
	return ans
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	print(proB(arr, k))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	m = n
	l = set(arr)
	for i in l:
		(j, s) = (0, 0)
		while j < n:
			if arr[j] != i:
				s += 1
				j += k
			else:
				j += 1
		m = min(m, s)
	print(m)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if len(set(a)) == 1:
		print(0)
		continue
	(f, h) = (101 * [0], 10000000000)
	for i in range(1, max(a) + 1):
		j = 0
		while j < n:
			if a[j] != i:
				break
			j += 1
		(x, j) = (1, j + k)
		while j < n:
			if a[j] != i:
				x += 1
				j += k
			else:
				j += 1
		if x < h:
			h = x
	print(h)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	final = 999999
	s = set()
	for i in range(n):
		s.add(a[i])
	for j in s:
		i = 0
		ans = 0
		while i < n:
			if a[i] != j:
				ans += 1
				i += k
			else:
				i += 1
		final = min(final, ans)
	print(final)


def color(arr, k):
	ans = []
	for maxi in set(arr):
		i = 0
		coast = 0
		while i < len(arr):
			if arr[i] != maxi:
				i += k
				coast += 1
			else:
				i += 1
		ans.append(coast)
	return min(ans)
t = int(input())
for i in range(t):
	(a, b) = map(int, input().strip().split())
	lst = list(map(int, input().strip().split()))
	print(color(lst, b))


def get_nums():
	return [int(x) for x in input().split()]

def solve(N, K, A):
	C = set(A)
	ans = float('inf')

	def paint(c):
		i = res = 0
		while i < N:
			if A[i] != c:
				res += 1
				i += K
			else:
				i += 1
		return res
	for c in C:
		ans = min(ans, paint(c))
	return ans
(T,) = get_nums()
for _ in range(T):
	(N, K) = get_nums()
	A = get_nums()
	print(solve(N, K, A))


def color(arr, n, k, x):
	res = 0
	i = 0
	while i < n:
		if arr[i] != x:
			res += 1
			i += k
		else:
			i += 1
	return res
tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cache = {}
	for i in arr:
		if i not in cache:
			cache[i] = 0
	for i in cache.keys():
		cache[i] = color(arr, n, k, i)
	print(min(cache.values()))


for tt in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	ans = 10 ** 9
	for m in s:
		i = 0
		cnt = 0
		while i < n:
			if l[i] == m:
				i += 1
			else:
				i += k
				cnt += 1
		ans = min(cnt, ans)
	print(ans)


import sys
t = int(input())
while t != 0:
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	A = sys.maxsize
	for i in s:
		j = 0
		ans = 0
		while j < a:
			if l[j] != i:
				ans += 1
				j += b
			else:
				j += 1
		A = min(ans, A)
	print(A)
	t -= 1


def solve(n, k, arr):
	set_color = list(set(arr))
	ans = 100000
	for c in set_color:
		effort = 0
		i = 0
		while i < n:
			if arr[i] != c:
				effort += 1
				i += k
			else:
				i += 1
		ans = min(ans, effort)
	return ans
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solve(n, k, arr))


from collections import Counter

def solve():
	(n, k) = map(int, input().split())
	houses = list(map(int, input().split()))
	result = float('inf')
	for color in set(houses):
		days = int()
		counter = int()
		while counter < n:
			if houses[counter] == color:
				counter += 1
			else:
				days += 1
				counter += k
		result = min(result, days)
	print(result)

def main():
	for _ in range(int(input())):
		solve()
main()


def find_days(a, color, k, n):
	i = 0
	days = 0
	while i < n:
		if a[i] != color:
			days += 1
			i += k
		else:
			i += 1
	return days
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	distinct = set(a)
	ans = 1000007
	for color in distinct:
		ans = min(ans, find_days(a, color, k, n))
	print(ans)


for _ in ' ' * int(input()):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 1000000000
	for x in set(a):
		i = 0
		ans2 = 0
		while i < n:
			if a[i] != x:
				ans2 += 1
				i += m - 1
			i += 1
		ans = min(ans, ans2)
	print(ans)


from math import *
for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	street = [int(x) for x in input().split()]
	minimum = inf
	colors = set()
	for color in street:
		colors.add(color)
	for color in colors:
		house = 0
		day = 0
		while house < n:
			if street[house] == color:
				house = house + 1
			else:
				house = house + k
				day = day + 1
		minimum = min(day, minimum)
	print(minimum)


import heapq
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = []
	c = max(l)
	for i in range(1, c + 1):
		y = 0
		j = 0
		while j < n:
			if l[j] != i:
				y += 1
				j += k
			else:
				j += 1
		heapq.heappush(x, y)
	print(x[0])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = max(a)
	ans = n // k + 1
	for i in range(1, mx + 1):
		cnt = 0
		j = 0
		while j < n:
			if a[j] != i:
				cnt += 1
				j += k
			else:
				j += 1
		ans = min(ans, cnt)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	m = n
	for i in range(min(c), max(c) + 1):
		j = 0
		cnt = 0
		while j < n:
			while j < n and c[j] == i:
				j += 1
			if j < n:
				cnt += 1
				j += k
		m = min(cnt, m)
	print(m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	sl = list(set(l))
	L = []
	for i in sl:
		co = 0
		j = 0
		while j in range(n):
			if l[j] != i:
				co += 1
				j = j + k - 1
			j += 1
		L.append(co)
	print(min(L))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	c = 0
	mn = 1000000000
	for i in s:
		j = 0
		c = 0
		while j < len(l):
			if l[j] != i:
				c += 1
				j += k
			else:
				j += 1
		if c < mn:
			mn = c
	print(mn)


for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	h = [int(x) for x in input().split()]
	keys = set(h)
	m = n // k + 1
	for tar in keys:
		i = 0
		count = 0
		while i < n:
			if h[i] == tar:
				i += 1
			else:
				count += 1
				i += k
				if count > m:
					break
		m = min(count, m)
	print(m)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sett = set()
	for c in arr:
		if c not in sett:
			sett.add(c)
	mini = n + 1
	for d in sett:
		u = 0
		cnt = 0
		while u < n:
			if arr[u] != d:
				cnt += 1
				u += k
			else:
				u += 1
		if mini > cnt:
			mini = cnt
	print(mini)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	houses = list(map(int, input().split()))
	colors = set(houses)
	days = n
	for c in colors:
		i = 0
		d = 0
		while True:
			if i >= n:
				break
			if houses[i] == c:
				i += 1
			else:
				i += k
				d += 1
		days = min(d, days)
	print(days)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	s = set(li)
	m = 0
	ans = n
	for cn in s:
		m = n
		cnt = 0
		i = 0
		while i < n:
			if li[i] != cn:
				i += k
				cnt += 1
			else:
				i += 1
		ans = min(ans, cnt)
	print(ans)


for _ in 'A' * int(input()):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	ans = n
	p = max(a)
	for i in range(1, p + 1):
		j = 0
		r = 0
		while j < n:
			if a[j] != i:
				j += k - 1
				r += 1
			j += 1
		ans = min(ans, r)
	print(ans)


import sys
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	tmp = 0
	res = sys.maxsize
	mx = max(li)
	for i in range(1, mx + 1):
		tmp = 0
		cnt = 0
		while cnt < n:
			if li[cnt] != i:
				tmp += 1
				cnt += k
			else:
				cnt += 1
		if tmp < res:
			res = tmp
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	s = set(c)
	ans = 999999999999999999999999999
	for main in s:
		boom = 0
		i = 0
		while i < n:
			if c[i] != main:
				try:
					for j in c[i:i + k]:
						if j != main:
							boom += 1
							i += k
							break
				except:
					for j in c[i:]:
						if j != main:
							boom += 1
							break
			else:
				i += 1
		if boom < ans:
			ans = boom
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = list(set(l))
	p = list()
	for i in s:
		c = 0
		j = 0
		while j < n:
			if l[j] != i:
				c += 1
				j += k
			else:
				j += 1
		p.append(c)
	print(min(p))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	s = set(c)
	day = 10 ** 5
	for i in s:
		m = 0
		x = 0
		while x < n:
			if c[x] == i:
				x += 1
			else:
				x += k
				m += 1
		day = min(day, m)
	print(day)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 10 ** 5 + 2
	for i in set(a):
		(j, cur) = (0, 0)
		while j < n:
			if a[j] == i:
				j += 1
			else:
				j += k
				cur += 1
		ans = min(ans, cur)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = set(a)
	m = 1000000
	for i in b:
		x = 0
		j = 0
		while j < n:
			if i != a[j]:
				x += 1
				j += k
			else:
				j += 1
		m = min(m, x)
	print(m)


import sys

def calci(mini, n, arr):
	idx = 0
	days = 0
	while True:
		if idx >= n:
			break
		if arr[idx] != mini:
			days += 1
			idx += k
		else:
			idx += 1
	return days
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	temp = set(arr)
	days = sys.maxsize
	for i in temp:
		x = calci(i, n, arr)
		if x < days:
			days = x
	print(days)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = {}
	a = list(map(int, input().split()))
	ma = 0
	mi = 0
	ans = 1000000000000
	for i in a:
		d[i] = d.get(i, 0) + 1
	t = sorted(d.items(), key=lambda kv: (kv[1], kv[0]), reverse=True)
	for j in t:
		mi = j[0]
		val = 0
		i = 0
		while i < n:
			if a[i] == mi:
				while i < n and a[i] == mi:
					i += 1
			if i < n:
				val += 1
				i += k
		ans = min(ans, val)
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	mas = list(map(int, input().split()))
	d = {}
	for j in mas:
		if j in d.keys():
			d[j] += 1
		else:
			d[j] = 1
	gans = 100000
	for s in d.keys():
		ans = 0
		j = 0
		while j < n:
			if mas[j] != s:
				ans += 1
				j += k
			else:
				j += 1
		gans = min(ans, gans)
	print(gans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	m = 10 ** 6
	for each in set(c):
		(ans, i) = (0, 0)
		while i < n:
			if c[i] != each:
				ans += 1
				i += k
			else:
				i += 1
		m = min(m, ans)
	print(m)


def max_count(arr):
	c = [0 for i in range(0, max(arr) + 1)]
	for i in arr:
		c[i] += 1
	maxi = c[0]
	ind = 0
	for i in range(1, max(arr) + 1):
		if maxi < c[i]:
			maxi = c[i]
			ind = i
	return ind
t = int(input())
for j in range(0, t):
	l1 = [int(x) for x in input().split()]
	n = l1[0]
	k = l1[1]
	l2 = [int(x) for x in input().split()]
	mini = 10 ** 9
	for c in range(1, max(l2) + 1):
		day = 0
		i = 0
		while i < n:
			if l2[i] == c:
				i += 1
			else:
				day += 1
				i = i + k
		if mini > day:
			mini = day
	print(mini)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	s = set(c)
	ans = 999999999
	for i in s:
		count = 0
		j = 0
		while j < n:
			if c[j] == i:
				j += 1
				continue
			else:
				count += 1
				j += k
		ans = min(ans, count)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = set(arr)
	minDays = n
	for v in s:
		day = 0
		j = 0
		while j < n:
			if arr[j] != v:
				day += 1
				j = j + k
			else:
				j += 1
		if minDays > day:
			minDays = day
	print(minDays)


from collections import defaultdict
t = int(input())
while t > 0:
	t -= 1
	(n, z) = map(int, input().split())
	a = list(map(int, input().split()))
	b = a.copy()
	b = set(b)
	b = list(b)
	final = 10000000000.0 + 1
	for num in b:
		cnt = 0
		i = 0
		while i < n:
			if a[i] != num:
				cnt += 1
				i += z
			else:
				i += 1
		final = min(final, cnt)
	print(final)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	a1 = 1000000
	a = set(l)
	for i in a:
		c = 0
		j = 0
		while j < n:
			if l[j] != i:
				j += k
				c += 1
			else:
				j += 1
		a1 = min(a1, c)
	print(a1)


n1 = int(input())
for i in range(n1):
	l1 = list(map(int, input().split()))
	n = l1[0]
	k = l1[1]
	l2 = list(map(int, input().split()))
	s1 = set(l2)
	l3 = []
	for i in s1:
		days = 0
		j = 0
		while j < n:
			if l2[j] != i:
				j += k
				days += 1
			else:
				j += 1
		l3.append(days)
	print(min(l3))


def Madara(v, k, c):
	q = 0
	s = 0
	while q < len(v):
		if v[q] == c:
			q += 1
			continue
		q += k
		s += 1
	return s

def Holo():
	(_, k) = map(lambda x: int(x), input().split())
	v = list(map(lambda x: int(x), input().split()))
	qm = 10000000000.0
	mc = max(v)
	for i in range(1, mc + 1):
		i = Madara(v, k, i)
		if i < qm:
			qm = i
	return qm
t = int(input())
for i in range(t):
	print(Holo())


def solve(n, k, seq):
	color = 1
	smallest = n
	while color <= max(seq):
		index = 0
		temp = 0
		while index < n:
			if seq[index] != color:
				temp += 1
				index += k
			else:
				index += 1
		if temp < smallest:
			smallest = temp
		color += 1
	return smallest
t = int(input())
for times in range(t):
	(n, k) = list(map(int, input().split()))
	print(solve(n, k, list(map(int, input().split()))))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = float('inf')
	s = set(l)
	for i in s:
		val = i
		c = 0
		j = 0
		while j < n:
			if l[j] != val:
				c += 1
				j = j + k
			else:
				j += 1
		ans = min(ans, c)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	x = max(l1)
	l2 = []
	for ii in set(l1):
		x = 0
		c = 0
		while x < n:
			if l1[x] == ii:
				x += 1
			else:
				x += k
				c += 1
		l2.append(c)
	print(min(l2))


for y in range(int(input())):
	(a, b) = map(int, input().split())
	lst = list(map(int, input().split()))
	st = list(set(lst))
	ans = [100001] * len(st)
	for i in range(len(st)):
		j = 0
		cnt = 0
		while j < a:
			if lst[j] == st[i]:
				j += 1
			else:
				cnt += 1
				j += b
		ans[i] = cnt
	print(min(ans))


from math import inf
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	a = set(arr)
	rs = 9999999
	for i in a:
		b = 0
		j = 0
		while j < len(arr):
			if arr[j] != i:
				b += 1
				j += k - 1
			j += 1
		if b < rs:
			rs = b
	print(rs)


t = int(input())
for i in range(t):
	ans = 10000000000
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = max(a)
	for j in range(1, p + 1):
		count = 0
		l = 0
		while l < n:
			if a[l] != j:
				count += 1
				l += k
			else:
				l += 1
		if count < ans:
			ans = count
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	colors = list(map(int, input().split()))
	color_kind = set(colors)
	days = []
	for color in color_kind:
		i = 0
		day = 0
		while i < len(colors):
			if colors[i] != color:
				day += 1
				i += k
			else:
				i += 1
		days.append(day)
	print(min(days))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	color = list(map(int, input().split()))
	max_ = float('inf')
	c = 0
	b = list(dict.fromkeys(color))
	for i in b:
		t = 0
		c = 0
		while c < n:
			if color[c] != i:
				t += 1
				c += k
			else:
				c += 1
		max_ = min(t, max_)
	print(max_)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	a = min(l)
	b = max(l)
	c = 100001
	for i in range(a, b + 1):
		if i in l:
			j = 0
			m = 0
			while j < n:
				if l[j] != i:
					m += 1
					j += k
				else:
					j += 1
			c = min(c, m)
	print(c)


try:
	inp = open('file.txt').readline
except:
	inp = input
t = int(inp().strip())
for _ in range(t):
	(n, k) = map(int, inp().strip().split(' '))
	arr = list(map(int, inp().strip().split(' ')))
	aset = set(arr)
	ans = int(1000000000.0)
	for hc in aset:
		color = hc
		days = 0
		i = 0
		while i < n:
			if arr[i] != color:
				kt = k
				days += 1
				i = i + k
			else:
				i += 1
		ans = min(days, ans)
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(j) for j in input().split()]
	col = []
	for j in range(len(a)):
		if a[j] not in col:
			col.append(a[j])
	mc = n
	c = 0
	j = 0
	for l in col:
		while j < n:
			if a[j] == l:
				j += 1
			else:
				j += k
				c += 1
		j = 0
		if mc > c:
			mc = c
		c = 0
	print(mc)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans = [10000000000.0] * 100
	A = list(map(int, input().split()))
	S = set(A)
	for c in S:
		ans[c - 1] = 0
		q = 0
		while q < n:
			if A[q] == c:
				q += 1
				continue
			else:
				ans[c - 1] += 1
				q += k
	print(min(ans))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	KQ = 10 ** 12
	set_value = {-1}
	for item in ls:
		set_value.add(item)
	set_value.remove(-1)
	for value in set_value:
		cur = 0
		kq = 0
		while cur < n:
			if ls[cur] != value:
				cur += k - 1
				kq += 1
			cur += 1
		KQ = min(KQ, kq)
	print(KQ)


t = int(input())
result = []
for _ in range(t):
	colours = [0] * 100
	colours_has = []
	inp = input().split()
	[n, k] = [int(i) for i in inp]
	inp = input().split()
	lst = [int(i) for i in inp]
	res = 100000000
	ind = 0
	for el in lst:
		el_ind = el - 1
		if not el in colours_has:
			colours_has.append(el)
		colours[el_ind] += 1
		ind += 1
	best_colour = colours.index(max(colours)) + 1
	for best_colour in colours_has:
		curr_res = 0
		i = 0
		while i < n:
			if lst[i] != best_colour:
				i += k - 1
				curr_res += 1
			i += 1
		if curr_res < res:
			res = curr_res
	result.append(res)
print(*result, sep='\n')


for l in range(int(input())):
	(n, k) = map(int, input().split())
	data = list(map(int, input().split()))
	result = 0
	colors = set()
	for i in data:
		colors.add(i)
	mini = float('inf')
	for i in colors:
		j = 0
		while j < n:
			if data[j] == i:
				j += 1
			else:
				result += 1
				j += k
		mini = min(result, mini)
		result = 0
	print(mini)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	m = float('inf')
	i = 0
	for e in list(dict.fromkeys(c)):
		ans = 0
		i = 0
		while i < n:
			if c[i] != e:
				ans += 1
				i += k
			else:
				i += 1
		m = min(ans, m)
	print(m)


import math
t = int(input())
for _ in range(t):
	arr = input().split()
	n = int(arr[0])
	k = int(arr[1])
	c = [int(i) for i in input().split()]
	l_ = list()
	for i in c:
		if not i in l_:
			l_.append(i)
	s_ = 9999999
	for l in l_:
		s = 0
		i = 0
		while i < len(c):
			if c[i] != l:
				j = i
				i = i + k
				s = s + 1
			else:
				i = i + 1
		if s < s_:
			s_ = s
	print(s_)


for test in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(dict.fromkeys(a))
	d = float('inf')
	i = 0
	for z in b:
		e = 0
		i = 0
		while i < n:
			if a[i] != z:
				e += 1
				i += k
			else:
				i += 1
		d = min(e, d)
	print(d)


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	coln = max(a)
	c = n
	for i in range(1, coln + 1):
		ct = 0
		j = 0
		while j < n:
			if a[j] != i:
				j += k
				ct += 1
			else:
				j += 1
		c = min(ct, c)
	print(c)


t = int(input())
for _ in range(t):
	global_ans = float('inf')
	(n, k) = map(int, input().split())
	houms_colours = list(map(int, input().split()))
	p = max(houms_colours)
	for colour in range(1, p + 1):
		x = 0
		ans = 0
		while x <= n - 1:
			if houms_colours[x] != colour:
				ans += 1
				x += k
			else:
				x += 1
		if ans < global_ans:
			global_ans = ans
	print(global_ans)


t = int(input())
for i in range(t):
	p = input().split()
	n = int(p[0])
	k = int(p[1])
	c = input().split()
	used = []
	nums = []
	nums.clear()
	used.clear()
	for j in c:
		if j not in used:
			color = j
			num = 0
			i = 0
			while i < n:
				if c[i] != color:
					num += 1
					i += k
				else:
					i += 1
			nums.append(num)
			used.append(j)
	nums.sort()
	print(nums.pop(0))