Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Chef is playing a game where he has an array $A$ of $N$ integers, and an integer $K$. He looks at every subarray of length $K$, and writes its sum on a piece of paper. If a number appears as the sum of multiple subarrays of length $K$, then he only writes down that number once.

Chef is lazy and doesn't like to write numbers. You, being a friend of Chef, want to modify the array such that Chef will only write one number on his paper. In one modification you can choose any index $i$ and replace $A_{i}$ with any integer.

You need to find the minimum number of modifications required.

------ Input ------
The first line contains an integer $T$, the number of test cases. Then the test cases follow.
Each test case contains two lines of input.
The first line contains two space-separated integers $N$, $K$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output ------
For each test case, output the answer in a single line.

------ Constraints  ------
$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
$1 ≤ A_{i} ≤ 10^{5}$
The sum of $N$ over all test cases does not exceed $5\cdot 10^{5}$.

----- Sample Input 1 ------ 
2

3 3 

1 2 3

2 1

4 6
----- Sample Output 1 ------ 
0

1
----- explanation 1 ------ 
Test Case 1: $K=3$ and there is only one subarray of length $3$, so no changes are required.

Test Case 2: $K=1$ and the subarrays of length $1$ are $[4]$ and $[6]$. So, at least one modification is required. One possible solution with only one modification is to change $A_{2}$ to $4$.

Difficulty: HARD
Tags: Combinatorics

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	t = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		d = {}
		q = i
		while q < n:
			if t[q] not in d:
				d[t[q]] = 1
			else:
				d[t[q]] += 1
			q += k
		l = list(d.values())
		s = sum(l)
		mx = max(l)
		ans += s - mx
	print(ans)


from collections import Counter as cc
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = [0 for _ in range(k)]
	freq = [cc() for _ in range(k)]
	for i in range(n):
		freq[i % k][l[i]] += 1
		c[i % k] += 1
	t = 0
	for (i, d) in enumerate(freq):
		t += c[i] - d.most_common(1)[0][1]
	print(t)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for j in range(k):
		s = {}
		if l[j] in s:
			s[l[j]] += 1
		else:
			s[l[j]] = 1
		z = j + k
		c = 1
		while z < n:
			if l[z] in s:
				s[l[z]] += 1
			else:
				s[l[z]] = 1
			z += k
			c += 1
		m = 0
		for (keys, v) in s.items():
			m = max(m, v)
		ans += c - m
	print(ans)


from collections import defaultdict
linp = lambda : list(map(int, input().split()))
iinp = lambda : int(input())
tinp = lambda : map(int, input().split())
rinp = lambda : range(int(input()))
dct = lambda : defaultdict(lambda : 0)
from collections import Counter
for _ in rinp():
	(n, k) = tinp()
	l = linp()
	z = [[] for _ in range(k)]
	for (i, e) in enumerate(l):
		m = (i + 1) % k
		z[m].append(e)
	ans = 0
	for ar in z:
		l = len(ar)
		if l == 0:
			continue
		c = Counter(ar).most_common(1)[0]
		c = c[1]
		ans += l - c
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		S = {}
		if arr[i] in S:
			S[arr[i]] += 1
		else:
			S[arr[i]] = 1
		j = i + k
		cnt = 1
		while j < n:
			if arr[j] in S:
				S[arr[j]] += 1
			else:
				S[arr[j]] = 1
			j += k
			cnt += 1
		mx = 0
		for (keys, v) in S.items():
			mx = max(mx, v)
		ans += cnt - mx
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	i = 0
	oper = 0
	while i < K:
		d = dict()
		for j in range(i, N, K):
			if A[j] in d.keys():
				d[A[j]] += 1
			else:
				d[A[j]] = 1
		oper += sum(d.values()) - max(d.values())
		i = i + 1
	print(oper)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = {i: defaultdict(int) for i in range(k)}
	for i in range(n):
		x[i % k][a[i]] += 1
	ans = 0
	for i in x.values():
		ans += sum(i.values()) - max(i.values())
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		tem = 0
		mod = 0
		dit = defaultdict(int)
		for j in range(i, n, k):
			dit[a[j]] += 1
			tem = max(tem, dit[a[j]])
			mod += 1
		ans += mod - tem
	print(ans)


import sys
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	res = 0
	for i in range(k):
		h = {}
		cnt = 1
		if l[i] in h:
			h[l[i]] += 1
		else:
			h[l[i]] = 1
		j = i + k
		while j < n:
			if l[j] in h:
				h[l[j]] += 1
			else:
				h[l[j]] = 1
			cnt += 1
			j += k
		ma = 0
		for i in h:
			ma = max(ma, h[i])
		res += cnt - ma
	print(res)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	changes = 0
	for i in range(k):
		mx = 0
		cnt = 0
		ddict = defaultdict(int)
		for j in range(i, n, k):
			ddict[arr[j]] += 1
			mx = max(mx, ddict[arr[j]])
			cnt += 1
		changes += cnt - mx
	print(changes)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for i in range(k):
		p = {}
		c = 0
		for j in range(i, n, k):
			if l[j] not in p:
				p[l[j]] = 1
			else:
				p[l[j]] += 1
			c = max(c, p[l[j]])
		s += c
	print(n - s)


def lin():
	return list(map(int, input().strip().split()))
test = int(input().strip())
for _ in range(test):
	(n, k) = lin()
	arr = lin()
	common_grps = [[] for i in range(k)]
	for i in range(n):
		common_grps[i % k].append(arr[i])
	ans = 0
	for row in common_grps:
		count = {}
		for item in row:
			if not count.get(item):
				count[item] = 0
			count[item] += 1
		maxi = 0
		for (val, val_count) in count.items():
			maxi = max(maxi, val_count)
		ans += len(row) - maxi
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = [0 for i in range(len(arr))]
	ans = 0
	for i in range(k):
		mapp = {}
		count = 0
		for j in range(i, n, k):
			if arr[j] not in mapp:
				mapp[arr[j]] = 1
			else:
				mapp[arr[j]] += 1
			m = int(mapp[arr[j]])
			count = max(count, m)
		ans += count
	print(n - ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		temp = {}
		count = 1
		if arr[i] in temp:
			temp[arr[i]] += 1
		else:
			temp[arr[i]] = 1
		j = i + k
		while j < n:
			if arr[j] in temp:
				temp[arr[j]] += 1
			else:
				temp[arr[j]] = 1
			count += 1
			j += k
		max_ = 0
		for i in temp:
			max_ = max(max_, temp[i])
		ans += count - max_
	print(ans)


from collections import Counter
import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k >= n:
		print(0)
		continue
	ans = 0
	for i in range(k):
		idx = i
		l = []
		while idx < n:
			l.append(arr[idx])
			idx = idx + k
		c = Counter(l)
		max_count = -1
		for (item, count) in c.items():
			if count > max_count:
				max_count = count
				maxi = item
		m = 0
		for i in range(len(l)):
			if l[i] != maxi:
				m = m + 1
		ans = ans + m
	print(ans)


import statistics
t = int(input())
while t > 0:
	t -= 1
	(N, K) = map(int, input().split())
	lst = list(map(int, input().split()))
	sum = 0
	l = [[] for i in range(K)]
	for i in range(len(lst)):
		m = (i + 1) % K
		l[m].append(lst[i])
	for i in range(K):
		if len(l[i]) <= 1:
			continue
		res = max(set(l[i]), key=l[i].count)
		sum = sum + len(l[i]) - l[i].count(res)
	print(sum)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	freq = [dict() for i in range(k)]
	for i in range(n):
		if arr[i] not in freq[i % k]:
			freq[i % k][arr[i]] = 1
		else:
			freq[i % k][arr[i]] += 1
	ans = 0
	for i in range(k):
		total = 0
		maxx = -1
		for (a, b) in freq[i].items():
			total += b
			maxx = max(maxx, b)
		ans += total - maxx
	print(ans)


def printModifs(l, N, K):
	modif = 0
	if K >= N:
		print(modif)
	else:
		for i in range(0, K):
			d = {}
			max = [l[i], 1]
			while i < N:
				if l[i] not in d:
					d[l[i]] = 1
				else:
					d[l[i]] += 1
					if d[l[i]] > max[1]:
						max = [l[i], d[l[i]]]
				i += K
			for x in d:
				if x != max[0]:
					modif += d[x]
		print(modif)
nt = int(input())
for i in range(0, nt):
	j = list(map(int, input().strip().split(' ')))
	N = j[0]
	K = j[1]
	l = list(map(int, input().strip().split(' ')))
	printModifs(l, N, K)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for j in range(0, k):
		freq = {}
		m = 1
		for l in range(j, n, k):
			if a[l] not in freq:
				freq[a[l]] = 1
			else:
				freq[a[l]] += 1
				if freq[a[l]] > m:
					m = freq[a[l]]
		ans += n // k + (1 if n % k >= j + 1 else 0) - m
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in range(k):
		l1 = l[i:n:k]
		d = {}
		for i in l1:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		c += len(l1) - max(d.values())
	print(c)


T = int(input())
for i in range(T):
	a = [int(s) for s in input().split()]
	(N, K) = (a[0], a[1])
	arr = [int(s) for s in input().split()]
	ans = 0
	for j in range(K):
		cur = j
		d = {}
		d[arr[cur]] = 0
		while cur < N:
			if arr[cur] in d.keys():
				d[arr[cur]] += 1
			else:
				d[arr[cur]] = 1
			cur += K
		maxi = max(d.values())
		ans += sum(list(d.values())) - maxi
	print(ans)


from collections import defaultdict
t = int(input())
for i in range(t):
	(n, k) = [int(j) for j in input().split()]
	ar = [int(j) for j in input().split()]
	c = 0
	if n <= k:
		pass
	else:
		st = 0
		while st < k:
			dt = defaultdict(lambda : 0)
			cnt = 0
			for idx in range(st, n, k):
				dt[ar[idx]] += 1
				cnt += 1
			c += cnt - dt[max(dt, key=lambda x: dt[x])]
			st += 1
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		c = 0
		has = dict()
		for j in range(i, len(a), k):
			if a[j] not in has:
				has[a[j]] = 1
			else:
				has[a[j]] += 1
			c = max(c, has[a[j]])
		ans += c
	print(n - ans)


try:
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		table = {}
		for i in range(k):
			table[i % k] = {}
			j = i
			while j < n:
				if arr[j] in table[i % k].keys():
					table[i % k][arr[j]] += 1
				else:
					table[i % k][arr[j]] = 1
				j += k
		ans = 0
		for i in range(k):
			total = 0
			maxx = -1
			for (num, cnt) in table[i].items():
				total += cnt
				maxx = max(maxx, cnt)
			ans += total - maxx
		print(ans)
except:
	pass


T = int(input())
for testcases in range(T):
	[N, K] = [int(x) for x in input().split()]
	A = [-1]
	A.extend([int(x) for x in input().split()])
	ret = 0
	for i in range(1, K + 1):
		j = i
		D = dict()
		ctr = maxx = 0
		while j <= N:
			D[A[j]] = D.get(A[j], 0) + 1
			ctr += 1
			maxx = max(maxx, D[A[j]])
			j += K
		ret += ctr - maxx
	print(ret)


from collections import Counter
t = int(input())
for r in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = len(set(l))
	c = 0
	j = 0
	while j < k:
		q = []
		for i in range(j, n, k):
			q.append(l[i])
		z = Counter(q)
		c += len(q) - max(z.values())
		j += 1
	print(c)


from sys import stdin, stdout
input = stdin.readline

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

def ii():
	return int(input())

def il():
	return list(map(int, input().split()))

def ins():
	return input()[:-1]
for _ in range(ii()):
	(n, k) = im()
	lis = il()
	count = 0
	for i in range(k):
		s = []
		j = i
		while j < n:
			s.append(lis[j])
			j += k
		mx = 0
		for i in s:
			mx = max(mx, s.count(i))
		count += len(s) - mx
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(0, k):
		list1 = []
		dict1 = {}
		while i <= n - 1:
			list1.append(arr[i])
			i += k
		a = set(list1)
		for qq in a:
			dict1[list1.count(qq)] = qq
		count += len(list1) - max(dict1)
	print(count)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		d = {}
		maxCount = 0
		c = 0
		for j in range(i, n, k):
			try:
				d[a[j]] += 1
			except:
				d[a[j]] = 1
			maxCount = max(maxCount, d[a[j]])
			c += 1
		ans += c - maxCount
	print(ans)


from sys import stdin, stdout

def find(dic):
	li = sorted(dic.values())
	return sum(li[0:-1])

def eva(arr, n, k):
	count = 0
	j = 0
	while j < k and k < n:
		i = j
		dic = {}
		while i < n:
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
			i += k
		else:
			count += find(dic)
			j += 1
	print(count)
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	arr = stdin.readline().split()
	eva(arr, n, k)


for _ in range(int(input())):
	l = input().split()
	(n, k) = (int(l[0]), int(l[1]))
	arr = [int(i) for i in input().split()]
	ans = 0
	if k == n:
		print(0)
		continue
	for i in range(k):
		d = {}
		for j in range(i, n, k):
			d[arr[j]] = d.get(arr[j], 0) + 1
		sums = sum(d.values())
		maxs = max(d.values())
		ans += sums - maxs
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == k:
		print(0)
		continue
	ans = 0
	for i in range(k):
		dic = {}
		count = 0
		while i < n:
			count += 1
			if a[i] in dic:
				dic[a[i]] += 1
			else:
				dic[a[i]] = 1
			i += k
		ans += count - max(dic.values())
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = [{} for i in range(k)]
	for i in range(len(arr)):
		if arr[i] in count[i % k]:
			count[i % k][arr[i]] += 1
		else:
			count[i % k][arr[i]] = 1
	total = 0
	for i in range(k):
		t = len(count[i])
		maxi = 0
		sumi = 0
		for key in count[i]:
			sumi += count[i][key]
			maxi = max(maxi, count[i][key])
		total += sumi - maxi
	print(total)


import statistics
T = int(input())
for i in range(T):
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	A = list(map(int, input().split()))
	ffans = 0
	L = [[] for i in range(K)]
	for i in range(N):
		L[i % K].append(A[i])
	for i in L:
		b = len(i)
		D = {}
		for j in i:
			if j not in D:
				D[j] = 1
			else:
				D[j] += 1
		c = max(D.values())
		ffans += b - c
	print(ffans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(map(int, input().split()))
	count = 0
	for j in range(k):
		dict = {}
		d_key = 0
		for i in range(j, n, k):
			s = str(c[i])
			if s in dict.keys():
				dict[s] += 1
			else:
				d_key += 1
				dict[s] = 1
		count += sum(dict.values()) - max(dict.values())
	if n == k:
		count = 0
	print(count)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	x = [int(i) for i in input().split()]
	ans = 0
	for i in range(k):
		total = max_val = mm = 0
		d = {}
		for j in range(i, n, k):
			if x[j] not in d:
				d[x[j]] = 1
			else:
				d[x[j]] += 1
		for key in d.keys():
			total += d[key]
			max_val = max(max_val, d[key])
		mm = total - max_val
		ans += mm
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		dt = dict()
		for j in range(i, n, k):
			if l[j] not in dt:
				dt[l[j]] = 1
			else:
				dt[l[j]] += 1
		mx = max(list(dt.values()))
		sm = sum(list(dt.values()))
		ans += sm - mx
	print(ans)


from collections import Counter

def subarray(l, k):
	count = 0
	if len(l) == k:
		return 0
	d = {}
	for i in range(k):
		d[i] = []
	for i in range(len(l)):
		d[i % k].append(l[i])
	for i in d:
		c = Counter(d[i])
		max_key = max(c, key=c.get)
		count += len(d[i]) - c[max_key]
	return count
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	print(subarray(l, k))


from math import *
from collections import defaultdict
R = lambda : list(map(int, input().split()))
MOD = 1000000007
for _ in range(int(input())):
	(n, k) = R()
	a = R()
	d = defaultdict(lambda : defaultdict(lambda : 0))
	for i in range(n):
		m = i % k
		d[m][a[i]] += 1
	ans = 0
	for (k, v) in d.items():
		(sm, mx) = (0, 0)
		for (x, y) in v.items():
			sm += v[x]
			mx = max(mx, v[x])
		ans += sm - mx
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		d = {}
		c = 0
		for j in range(i, n, k):
			c += 1
			if l[j] not in d.keys():
				d[l[j]] = 1
			else:
				d[l[j]] += 1
		x = max(d.values())
		ans += c - x
	print(ans)


from itertools import combinations
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for j in range(k):
		w = {}
		p = j
		while p < n:
			if a[p] not in w:
				w[a[p]] = 1
			else:
				w[a[p]] += 1
			p += k
		s = list(w.values())
		r = sum(s)
		d = max(s)
		c = c + r - d
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	b = 0
	for i in range(k):
		c = 0
		freq = {}
		for j in range(i, n, k):
			c = c + 1
			m = list1[j]
			if m in freq:
				freq[m] += 1
			else:
				freq[m] = 1
		a = max(freq, key=freq.get)
		b = b + (c - freq.get(a))
	print(b)


from collections import Counter

def sol(a, n, k):
	(d, change) = ({i: a[i::k] for i in range(k)}, 0)
	for i in range(k):
		change += len(d[i]) - Counter(d[i]).most_common()[0][1]
	return change
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(sol(a, n, k))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	coun = 0
	l = []
	for u in range(k):
		l.append([])
	for i in range(n):
		l[i % k].append(a[i])
	for q in range(k):
		res = max(set(l[q]), key=l[q].count)
		b = l[q].count(res)
		coun += len(l[q]) - b
	print(coun)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in range(k):
		j = 0
		frequency = {}
		total = 0
		while i + j * k < n:
			frequency[l[i + j * k]] = frequency.get(l[i + j * k], 0) + 1
			total = total + 1
			j += 1
		count += total - max(list(frequency.values()))
	print(count)


from sys import stdin, stdout

def csubs(n, k, arr):
	d = dict()
	for i in range(n):
		d[i % k] = {}
	for i in range(n):
		curr = arr[i]
		d[i % k][curr] = d[i % k].get(curr, 0) + 1
	ans = 0
	for i in range(k):
		(total, m) = (0, -1)
		for j in d[i]:
			total += d[i][j]
			m = max(d[i][j], m)
		ans += total - m
	return ans
t = int(stdin.readline().strip())

def takeInput():
	arr = list(map(int, stdin.readline().strip().split(' ')))
	return arr
for i in range(t):
	arr = takeInput()
	(n, k) = (arr[0], arr[1])
	arr = takeInput()
	print(csubs(n, k, arr))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	i = 0
	while i < k:
		d = dict()
		j = i
		while j < n:
			d[a[j]] = 0
			j += k
		j = i
		maxx = 0
		while j < n:
			d[a[j]] += 1
			if maxx < d[a[j]]:
				maxx = d[a[j]]
			j += k
		tot = (n - i - 1) // k + 1
		ans += tot - maxx
		i += 1
	print(ans)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		freq = {}
		total = 0
		for j in range(i, n, k):
			freq[a[j]] = freq.get(a[j], 0) + 1
			total = total + 1
		max_freq = max(freq.values())
		ans = ans + (total - max_freq)
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	ar = [int(i) for i in input().split()]
	d = [[] for i in range(k)]
	for i in range(n):
		d[i % k].append(ar[i])
	ans = 0
	for i in range(k):
		(maxi, arr) = (0, d[i])
		temp = {}
		for j in arr:
			if j in temp:
				temp[j] += 1
			else:
				temp[j] = 1
			maxi = max(maxi, temp[j])
		ans += len(arr) - maxi
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		cnt = 1
		dic = {arr[i]: 1}
		for j in range(i + k, n, k):
			if arr[j] in dic:
				dic[arr[j]] += 1
			else:
				dic[arr[j]] = 1
			cnt += 1
		f = max(dic.values())
		ans += cnt - f
	print(ans)


def find(start, arr):
	d = {}
	for i in range(start, n, k):
		if arr[i] in d.keys():
			d[arr[i]] += 1
		else:
			d[arr[i]] = 1
	return d
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = 0
	for i in range(k):
		dic = find(i, arr)
		res += sum(dic.values()) - max(dic.values())
	print(res)


for t in range(int(input())):
	(n, k) = tuple(map(int, input().strip().split()))
	a = tuple(map(int, input().strip().split()))
	s = [[] for i in range(k)]
	for i in range(n):
		s[i % k].append(a[i])
	ans = 0
	for sa in s:
		d = dict()
		for v in sa:
			if v not in d:
				d[v] = 0
			d[v] += 1
		f = 0
		for i in d:
			f = max(f, d[i])
		ans += len(sa) - f
	print(ans)


t = int(input())
while t:
	ans = 0
	(n, k) = [int(x) for x in input().split()]
	d = {}
	l = [int(x) for x in input().split()]
	for i in range(n):
		if i % k in d:
			d[i % k].append(l[i])
		else:
			d[i % k] = [l[i]]
	for x in d.keys():
		maxx = 0
		for i in range(len(d[x])):
			p = d[x].count(d[x][i])
			maxx = max(p, maxx)
		ans += len(d[x]) - maxx
	print(ans)
	t = t - 1


def csubs(n, k, arr):
	ans = 0
	for i in range(0, k):
		d = {}
		c = 0
		for j in range(i, n, k):
			if arr[j] not in d:
				d[arr[j]] = 1
			else:
				d[arr[j]] += 1
			c += 1
		m = max(d.values())
		ans += c - m
	print(ans)
t = int(input())
for _ in range(t):
	a = list(map(int, input().split()))
	n = a[0]
	k = a[1]
	arr = list(map(int, input().split()))
	csubs(n, k, arr)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		j = i
		h = {}
		c = 0
		while j < n:
			try:
				h[l[j]] += 1
			except:
				h[l[j]] = 1
			c += 1
			j += k
		m = 0
		for i in h.values():
			if i > m:
				m = i
		ans += c - m
	print(ans)


t = int(input())
for test in range(t):
	(n, k) = list(map(int, input().split()))
	num = list(map(int, input().split()))
	maxN = max(num)
	l = [{} for i in range(k)]
	for i in range(n):
		if l[i % k].get(num[i]) is None:
			l[i % k][num[i]] = 1
		else:
			l[i % k][num[i]] += 1
	minI = 0
	for i in l:
		val = i.values()
		maxC = max(val)
		total = sum(val)
		minI += total - maxC
	print(minI)


from collections import defaultdict, Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = defaultdict(list)
	ans = 0
	for j in range(n):
		d[j % k].append(arr[j])
	for j in range(k):
		ans += len(d[j]) - max(Counter(d[j]).values())
	print(ans)


t = int(input())
while t:
	t -= 1
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		tmp = []
		j = i
		while j < n:
			tmp.append(l[j])
			j += k
		maxi = 0
		for i in set(tmp):
			maxi = max(maxi, tmp.count(i))
		ans += len(tmp) - maxi
	print(ans)


def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
try:
	t = int(input())
	p = 10 ** 9 + 7
	while t:
		t -= 1
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		cnt = 0
		for i in range(k):
			dic = {}
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
			j = i + k
			cnt += 1
			a = arr[i]
			a_freq = dic[arr[i]]
			while j < n:
				if arr[j] in dic:
					dic[arr[j]] += 1
					cnt += 1
				else:
					dic[arr[j]] = 1
					cnt += 1
				if a_freq < dic[arr[j]]:
					a = arr[j]
					a_freq = dic[arr[j]]
				j += k
			cnt -= a_freq
		print(cnt)
except:
	pass


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	lst = [[] for j in range(k)]
	for j in range(n):
		lst[j % k].append(arr[j])
	ans = 0
	for j in range(k):
		ans += len(lst[j]) - lst[j].count(max(set(lst[j]), key=lst[j].count))
	print(ans)


from collections import defaultdict
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == k:
		print(0)
		continue
	ans = 0
	for i in range(k):
		d = defaultdict(int)
		count = 0
		for j in range(i, n, k):
			count += 1
			d[a[j]] += 1
		ans += count - max(d.values())
	print(ans)


from collections import Counter
try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		c = 0
		for x in range(k):
			l1 = []
			for y in range(x, n, k):
				l1.append(l[y])
			res = Counter(l1).most_common(1)[0][0]
			c += len(l1) - l1.count(res)
		print(c)
except:
	pass


t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	a = tuple(map(int, input().split()))
	if k == n:
		print(0)
	else:
		dic = {}
		cnt = 0
		element = 0
		maxi = 0
		i = 0
		while i < k:
			j = i
			dic = {}
			element = 0
			maxi = 0
			while j < n:
				if a[j] not in dic:
					dic[a[j]] = 1
				else:
					dic[a[j]] += 1
				if dic[a[j]] > maxi:
					maxi = dic[a[j]]
				element += 1
				j += k
			cnt += element - maxi
			i += 1
		print(cnt)


from collections import *
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	store = defaultdict(list)
	for i in range(n):
		store[i % k].append(arr[i])
	ans = 0
	for i in range(k):
		ll = store[i]
		ct = Counter(ll)
		mc = ct.most_common(1)[0][1]
		ans += len(ll) - mc
	print(ans)


import math
from collections import deque, defaultdict
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	d = defaultdict(list)
	for i in range(n):
		d[i % k].append(a[i])
	ans = 0
	for i in range(k):
		res = max(set(d[i]), key=d[i].count)
		ans += len(d[i]) - d[i].count(res)
	print(ans)


def get_max_freq(arr):
	max_freq = 0
	freq = {}
	for num in arr:
		if num in freq:
			freq[num] += 1
		else:
			freq[num] = 1
		max_freq = max(max_freq, freq[num])
	return max_freq
test_cases = int(input())
for test in range(test_cases):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	result = 0
	for i in range(k):
		sub_arr = arr[i::k]
		max_freq = get_max_freq(sub_arr)
		result += len(sub_arr) - max_freq
	print(result)


def calOperations(dic):
	(Sum, Max) = (0, 0)
	for (num, value) in dic.items():
		if Max < value:
			Max = value
		Sum += value
	return Sum - Max
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	opr = 0
	for i in range(k):
		dic = {}
		for j in range(i, n, k):
			if arr[j] not in dic:
				dic[arr[j]] = 0
			dic[arr[j]] += 1
		opr += calOperations(dic)
	print(opr)


from collections import defaultdict
T = int(input())
for t in range(T):
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	counts = [defaultdict(int) for i in range(K)]
	for i in range(N):
		counts[i % K][A[i]] += 1
	replacements = 0
	for i in range(K):
		max_count = -1
		total = 0
		for (key, value) in counts[i].items():
			total += value
			if value > max_count:
				max_count = value
		replacements += total - max_count
	print(replacements)


from itertools import groupby
from collections import defaultdict, Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == k:
		print(0)
		continue
	ans = 0
	d = defaultdict(list)
	for i in range(k):
		j = i
		while j < n:
			d[i].append(l[j])
			j += k
	for i in d:
		f = defaultdict(int)
		mx = 0
		c = 0
		for j in d[i]:
			f[j] += 1
			mx = max(mx, f[j])
			c += 1
		ans += c - mx
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = [{} for r in range(k)]
	for j in range(n):
		if arr[j] in l[j % k]:
			l[j % k][arr[j]] += 1
		else:
			l[j % k][arr[j]] = 1
	count = 0
	for d in l:
		count += sum(d.values()) - max(d.values())
	print(count)


t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	s = 0
	for i in range(k):
		j = i + k
		frq = {}
		frq[A[i]] = 1
		t = 1
		while j < n:
			frq[A[j]] = frq.get(A[j], 0) + 1
			j += k
			t += 1
		l = max(frq.values())
		s += t - l
	print(s)


def fun1(S):
	R = list(set(S))
	res = []
	for i in range(0, len(R)):
		y = S.count(R[i])
		res.append(y)
	x = max(res)
	res.remove(x)
	return sum(res)

def fun(A, K):
	res = []
	cnt = 0
	for i in range(0, K):
		S = []
		j = i
		while j < len(A):
			S.append(A[j])
			j += K
		cnt += fun1(S)
	return cnt
T = int(input())
for i in range(0, T):
	(N, K) = map(int, input().split())
	A = [int(x) for x in input().split()]
	print(fun(A, K))


t = int(input())
while t:
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	d = {}
	changes = 0
	for i in range(N):
		if i % K in d.keys():
			if A[i] in d[i % K].keys():
				d[i % K][A[i]] += 1
			else:
				d[i % K][A[i]] = 1
		else:
			d[i % K] = {}
			d[i % K][A[i]] = 1
	d2 = {}
	for key in d.keys():
		maxoccur = 0
		value = 0
		for subkey in d[key].keys():
			if maxoccur < d[key][subkey]:
				maxoccur = d[key][subkey]
				value = subkey
		d2[key] = value
	for i in range(N):
		if A[i] != d2[i % K]:
			changes += 1
	print(changes)
	t -= 1


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
from collections import defaultdict, Counter
for _ in range(RI()):
	(N, K) = RMI()
	vals = RMI()
	if N <= K:
		print(0)
	else:
		x = 0
		for i in range(K):
			curr = vals[i::K]
			currc = Counter(curr)
			x += len(curr) - currc[currc.most_common(1)[0][0]]
		print(x)


import sys
input = sys.stdin.readline
import math
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	(n, k) = invr()
	l = inlt()
	c = 0
	s = 0
	for i in range(k):
		d = {}
		o = 0
		for j in range(i, n, k):
			o += 1
			if l[j] not in d:
				d[l[j]] = 1
			else:
				d[l[j]] += 1
		m = 0
		for i in d:
			if d[i] > m:
				m = d[i]
		c += o - m
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(k):
		d = {}
		max_so_far = 1
		total = 0
		for j in range(i, n, k):
			total += 1
			if arr[j] in d:
				d[arr[j]] += 1
				max_so_far = max(max_so_far, d[arr[j]])
			else:
				d[arr[j]] = 1
		ans += total - max_so_far
	print(ans)


from collections import defaultdict

def minchange(arr, n, k):
	if n == k:
		return 0
	ans = 0
	for i in range(k):
		mp = defaultdict(int)
		count = 0
		for j in range(i, n, k):
			mp[arr[j]] += 1
			count = max(count, mp[arr[j]])
		ans += count
	return n - ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	print(minchange(arr, n, k))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nos = list(map(int, input().split()))
	d = {}
	for i in range(n):
		x = i % k
		if x in d:
			if nos[i] in d[x]:
				d[x][nos[i]] += 1
			else:
				d[x][nos[i]] = 1
		else:
			d[x] = {}
			d[x][nos[i]] = 1
	for i in range(k):
		x = -1
		rep = -1
		for candidate in d[i]:
			if d[i][candidate] > x:
				rep = candidate
				x = d[i][candidate]
		d[i] = rep
	ans = 0
	for i in range(n):
		if nos[i] != d[i % k]:
			ans += 1
	print(ans)