The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $k$. Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1 = b_i$, $a_2 = b_{i + 1}$, $a_3 = b_{i + 2}$, ..., $a_{|a|} = b_{i + |a| - 1}$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string "RGBRGBRGB ...".


-----Example-----
Input
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

Output
1
0
3



-----Note-----

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Amortized analysis

Data structures

Implementation


Solutions:
import sys
input = lambda : sys.stdin.readline().strip()
nxt = {'R': 'G', 'G': 'B', 'B': 'R'}
T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split()))
	s = input()
	res = []
	for start in ['R', 'G', 'B']:
		mis = []
		cur = start
		for j in range(k):
			if s[j] != cur:
				mis.append(1)
			else:
				mis.append(0)
			cur = nxt[cur]
		res.append(sum(mis))
		for j in range(k, n):
			res.append(res[-1] + int(s[j] != cur) - mis[j - k])
			if s[j] != cur:
				mis.append(1)
			else:
				mis.append(0)
			cur = nxt[cur]
	print(min(res))


import sys
import math
from collections import defaultdict
input = sys.stdin.readline

def min_to_change(s, n, k):
	strings = ['RGB', 'GBR', 'BRG']
	to_change = [0, 0, 0]
	pos = [0, 0, 0]
	for i in range(k):
		for x in range(3):
			if s[i] != strings[x][pos[x]]:
				to_change[x] += 1
			pos[x] = (pos[x] + 1) % 3
	res = min(to_change)
	curr = 1
	while curr + k - 1 < n:
		to_change_new = [0, 0, 0]
		for x in range(3):
			similar = (x + 2) % 3
			val = to_change[similar]
			if s[curr - 1] != strings[similar][0]:
				val -= 1
			if s[curr + k - 1] != strings[x][(k - 1) % 3]:
				val += 1
			to_change_new[x] = val
		to_change = to_change_new
		res = min(res, *to_change)
		curr += 1
	return res

def main():
	q = int(input())
	for _ in range(q):
		(n, k) = map(int, input().split())
		s = input()
		print(min_to_change(s, n, k))
main()


def naiveSolve():
	return

def getMinChanges(s, t, n, k):
	arr = [0] * n
	for i in range(n):
		if s[i] != t[i]:
			arr[i] = 1
	p = arr
	for i in range(1, n):
		p[i] += p[i - 1]

	def query(l, r):
		res = p[r]
		if l - 1 >= 0:
			res -= p[l - 1]
		return res
	ans = inf
	for l in range(n):
		r = l + k - 1
		if r == n:
			break
		ans = min(ans, query(l, r))
	return ans

def main():
	q = int(input())
	allans = []
	for _ in range(q):
		(n, k) = readIntArr()
		s = input()
		ans = inf
		m = (n + 2) // 3
		testStrings = [('RGB' * m)[:n], ('GBR' * m)[:n], ('BRG' * m)[:n]]
		for t in testStrings:
			ans = min(ans, getMinChanges(s, t, n, k))
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

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

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(l, r):
	print('? {} {}'.format(l, r))
	sys.stdout.flush()
	return int(input())

def answerInteractive(x):
	print('! {}'.format(x))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
for _ in range(int(input())):
	(n, k) = map(int, sys.stdin.readline().split())
	a = sys.stdin.readline()
	if n == 1:
		print(0)
	else:
		next = a[:2]
		parsum1 = [0 for _ in range(n + 1)]
		parsum2 = [0 for _ in range(n + 1)]
		parsum3 = [0 for _ in range(n + 1)]
		check = 'RGB'
		i1 = 0
		s1 = 0
		i2 = 1
		s2 = 0
		i3 = 2
		s3 = 0
		for i in range(n):
			if a[i] != check[i1]:
				s1 += 1
			if a[i] != check[i2]:
				s2 += 1
			if a[i] != check[i3]:
				s3 += 1
			i1 = i1 + 1 if i1 + 1 < 3 else 0
			i2 = i2 + 1 if i2 + 1 < 3 else 0
			i3 = i3 + 1 if i3 + 1 < 3 else 0
			parsum1[i + 1] = s1
			parsum2[i + 1] = s2
			parsum3[i + 1] = s3
		mn1 = n
		mn2 = n
		mn3 = n
		i = 1
		while 1:
			mxRange = i + k - 1
			if mxRange <= n:
				mn1 = min(parsum1[mxRange] - parsum1[i - 1], mn1)
				mn2 = min(parsum2[mxRange] - parsum2[i - 1], mn2)
				mn3 = min(parsum3[mxRange] - parsum3[i - 1], mn3)
			else:
				break
			i += 1
		sys.stdout.write('{}\n'.format(min(mn1, mn2, mn3)))


import sys

def main():

	def diff(s, l):
		ret1 = [0 for k in range(len(s))]
		for k in range(len(s)):
			if k % 3 == 0 and s[k] != 'R':
				ret1[k] = 1
			if k % 3 == 1 and s[k] != 'G':
				ret1[k] = 1
			if k % 3 == 2 and s[k] != 'B':
				ret1[k] = 1
		ret2 = [0] * len(s)
		for k in range(len(s)):
			if k % 3 == 0 and s[k] != 'G':
				ret2[k] = 1
			if k % 3 == 1 and s[k] != 'B':
				ret2[k] = 1
			if k % 3 == 2 and s[k] != 'R':
				ret2[k] = 1
		ret3 = [0] * len(s)
		for k in range(len(s)):
			if k % 3 == 0 and s[k] != 'B':
				ret3[k] = 1
			if k % 3 == 1 and s[k] != 'R':
				ret3[k] = 1
			if k % 3 == 2 and s[k] != 'G':
				ret3[k] = 1
		s1 = [0] * (len(s) + 1)
		s2 = [0] * (len(s) + 1)
		s3 = [0] * (len(s) + 1)
		for k in range(1, n + 1):
			s1[k] = s1[k - 1] + ret1[k - 1]
			s2[k] = s2[k - 1] + ret2[k - 1]
			s3[k] = s3[k - 1] + ret3[k - 1]
		ans = 1000000
		for k in range(len(s) - l):
			ans = min(ans, s1[k + l] - s1[k], s2[k + l] - s2[k], s3[k + l] - s3[k])
		return ans
	input = sys.stdin.readline
	q = int(input())
	for query in range(q):
		(n, k) = list(map(int, input().split()))
		s = input()
		print(diff(s, k))

def __starting_point():
	main()
__starting_point()


a = int(input())
ot = ''
for i in range(a):
	(b, c) = list(map(int, input().split()))
	s = input()
	pref = [0] * (b + 1)
	pref1 = [0] * (b + 1)
	pref2 = [0] * (b + 1)
	n = 'RGB'
	n1 = 'GBR'
	n2 = 'BRG'
	for j in range(b):
		pref[j + 1] = pref[j]
		if s[j] != n[j % 3]:
			pref[j + 1] += 1
		pref1[j + 1] = pref1[j]
		if s[j] != n1[j % 3]:
			pref1[j + 1] += 1
		pref2[j + 1] = pref2[j]
		if s[j] != n2[j % 3]:
			pref2[j + 1] += 1
	mi = 1000000000
	for j in range(c, b + 1):
		mi = min(pref[j] - pref[j - c], pref1[j] - pref1[j - c], pref2[j] - pref2[j - c], mi)
	mi = min(pref[-1], pref1[-1], pref2[-1], mi)
	ot += str(mi) + '\n'
print(ot)


import sys

def main():
	N = int(sys.stdin.readline().strip())
	for _ in range(N):
		(n, k) = [int(x) for x in sys.stdin.readline().strip().split()]
		s = sys.stdin.readline().strip()
		S = 'RGB'
		err = [[0] for _ in S]
		res = [n for i in range(len(S))]
		for (i, c) in enumerate(s):
			for j in range(3):
				prev = err[j][-1]
				err[j].append(prev + (0 if S[(i + j) % 3] == c else 1))
				if i + 1 >= k:
					res[j] = min(res[j], err[j][-1] - err[j][-k - 1])
		print(min(*res))
main()


import sys
input = sys.stdin.readline
rgb = 'RGB'
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().rstrip()
	costs = [[0] * (n + 1) for i in range(3)]
	for i in range(3):
		for j in range(n):
			costs[i][j + 1] = costs[i][j] + (1 if rgb[(i + j) % 3] != s[j] else 0)
	ans = 10 ** 18
	for (i, j) in zip(range(n), range(k, n + 1)):
		for k in range(3):
			if ans > costs[k][j] - costs[k][i]:
				ans = costs[k][j] - costs[k][i]
	print(ans)


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	s = input()
	D = K
	t = 'RGB'
	if K == 1:
		D = 0
	else:
		for m in range(3):
			d = 0
			a = [0] * N
			for i in range(N):
				if s[i] != t[(m + i) % 3]:
					a[i] = 1
				d = d + a[i]
				if i > K - 1:
					d = d - a[i - K]
				if d < D and i >= K - 1:
					D = d
				if D == 0:
					break
			if D == 0:
				break
	print(D)


import math
inf = 10 ** 5
import sys
for _ in range(int(input())):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	s = '$' + sys.stdin.readline().split('\n')[0]
	r = [0 for i in range(n + 1)]
	g = [0 for i in range(n + 1)]
	b = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		if s[i] == 'R':
			r[i] = r[max(0, i - 3)] + 1
		else:
			r[i] = r[max(0, i - 3)]
		if s[i] == 'G':
			g[i] = g[max(0, i - 3)] + 1
		else:
			g[i] = g[max(0, i - 3)]
		if s[i] == 'B':
			b[i] = b[max(0, i - 3)] + 1
		else:
			b[i] = b[max(0, i - 3)]

	def check(i, k):
		m = 10 ** 12
		rr = 0
		gg = 0
		bb = 0
		if k % 3 == 1:
			rr = 1
		if k % 3 == 2:
			rr = 1
			gg = 1
		kk = k
		m = min(m, k // 3 + rr - (r[i + (k - 1) // 3 * 3] - r[max(i - 3, 0)]) + k // 3 + gg - (g[i + 1 + (k - 2) // 3 * 3] - g[max(i - 2, 0)]) + k // 3 - (b[i + 2 + (k - 3) // 3 * 3] - b[max(i - 1, 0)]))
		m = min(m, k // 3 + rr - (g[i + (k - 1) // 3 * 3] - g[max(i - 3, 0)]) + k // 3 + gg - (b[i + 1 + (k - 2) // 3 * 3] - b[max(i - 2, 0)]) + k // 3 - (r[i + 2 + (k - 3) // 3 * 3] - r[max(i - 1, 0)]))
		m = min(m, k // 3 + rr - (b[i + (k - 1) // 3 * 3] - b[max(i - 3, 0)]) + k // 3 + gg - (r[i + 1 + (k - 2) // 3 * 3] - r[max(i - 2, 0)]) + k // 3 - (g[i + 2 + (k - 3) // 3 * 3] - g[max(i - 1, 0)]))
		return m
	m = 10 ** 13
	for i in range(n - k + 1):
		m = min(m, check(i + 1, k))
	print(max(m, 0))


import sys
input = sys.stdin.readline
q = int(input())
for i in range(q):
	(n, k) = map(int, input().split())
	s = input()[:n]
	if k == 1:
		print(0)
		continue
	rgb = [0, 0, 0]
	a = 1
	for (j, c) in enumerate(s):
		if c == 'R':
			rgb[j % 3] += 1
		elif c == 'G':
			rgb[(j - 1) % 3] += 1
		else:
			rgb[(j - 2) % 3] += 1
		if j + 1 >= k:
			a = max(a, max(rgb))
			t = s[j - k + 1]
			if t == 'R':
				rgb[(j - k + 1) % 3] -= 1
			elif t == 'G':
				rgb[(j - k) % 3] -= 1
			else:
				rgb[(j - k - 1) % 3] -= 1
			if a == k:
				print(0)
				break
	else:
		print(k - a)


import sys
t = int(sys.stdin.readline())
x = 'RGB'
y = 'GBR'
z = 'BRG'
for i in range(t):
	(n, k) = list(map(int, sys.stdin.readline().strip().split()))
	a = sys.stdin.readline().strip()
	xk = x
	yk = y
	zk = z
	op = 2001
	xd = []
	yd = []
	zd = []
	xdc = 0
	ydc = 0
	zdc = 0
	b = a
	for j in range(k):
		if b[j] != xk[j % 3]:
			xd.append(1)
			xdc += 1
		else:
			xd.append(0)
		if b[j] != yk[j % 3]:
			yd.append(1)
			ydc += 1
		else:
			yd.append(0)
		if b[j] != zk[j % 3]:
			zdc += 1
			zd.append(1)
		else:
			zd.append(0)
	op = min(xdc, ydc, zdc)
	for j in range(k, n):
		if b[j] != xk[j % 3]:
			xd.append(1)
			xdc += 1
		else:
			xd.append(0)
		if b[j] != yk[j % 3]:
			yd.append(1)
			ydc += 1
		else:
			yd.append(0)
		if b[j] != zk[j % 3]:
			zdc += 1
			zd.append(1)
		else:
			zd.append(0)
		xdc -= xd[j - k]
		ydc -= yd[j - k]
		zdc -= zd[j - k]
		op = min(op, xdc, ydc, zdc)
	print(op)


from sys import stdin
input = stdin.readline
q = int(input())
for _ in range(q):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	start = [0] * n
	for i in range(n):
		if s[i] == 'R':
			start[i] = i % 3
		elif s[i] == 'G':
			start[i] = (i - 1) % 3
		else:
			start[i] = (i - 2) % 3
	act = [0] * 3
	for i in range(k):
		act[start[i]] += 1
	res = max(act)
	for i in range(k, n):
		act[start[i]] += 1
		act[start[i - k]] -= 1
		res = max([act[start[i]], res])
	print(k - res)


queries = int(input())
rgb = ['R', 'G', 'B']
(r_idx, g_idx, b_idx) = (0, 1, 2)
ret = ''
for q in range(queries):
	(n, k) = list(map(int, input().split()))
	s = input()
	if n == 1 or k == 1:
		ret += '0\n'
		continue
	num_windows = n - k + 1
	r_arr = [0] * num_windows
	g_arr = [0] * num_windows
	b_arr = [0] * num_windows
	min_cost = [0] * num_windows
	for i in range(num_windows):
		r_start = g_start = b_start = 0
		if i == 0:
			for j in range(k):
				if s[i + j] != rgb[(j + r_idx) % 3]:
					r_start += 1
				if s[i + j] != rgb[(j + g_idx) % 3]:
					g_start += 1
				if s[i + j] != rgb[(j + b_idx) % 3]:
					b_start += 1
		else:
			j = k - 1
			r_start = b_arr[i - 1] - (1 if s[i - 1] != 'B' else 0) + (1 if s[i + j] != rgb[(j + r_idx) % 3] else 0)
			g_start = r_arr[i - 1] - (1 if s[i - 1] != 'R' else 0) + (1 if s[i + j] != rgb[(j + g_idx) % 3] else 0)
			b_start = g_arr[i - 1] - (1 if s[i - 1] != 'G' else 0) + (1 if s[i + j] != rgb[(j + b_idx) % 3] else 0)
		r_arr[i] = r_start
		g_arr[i] = g_start
		b_arr[i] = b_start
		min_cost[i] = min(r_start, g_start, b_start)
		if min_cost[i] == 0:
			break
	ret += str(min(min_cost)) + '\n'
print(ret)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, K) = getInts()
	best = 10 ** 9
	S = listStr()
	A = []
	for s in S:
		if s == 'R':
			A.append(0)
		elif s == 'G':
			A.append(1)
		else:
			A.append(2)
	for option in range(3):
		P = [0]
		curr = 0
		for (i, a) in enumerate(A):
			if (a + option) % 3 == i % 3:
				curr += 1
			P.append(curr)
		for i in range(K, N + 1):
			best = min(best, K - (P[i] - P[i - K]))
	return best
for _ in range(getInt()):
	print(solve())


import sys
from sys import stdin, stdout
import bisect
import math
import heapq

def modinv(n, p):
	return pow(n, p - 2, p)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())
import math

def Divisors(n):
	l = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	return l

def ch(x, y, z, n):
	a = []
	for i in range(n):
		if i % 3 == 0:
			a.append(x)
		elif i % 3 == 1:
			a.append(y)
		else:
			a.append(z)
	return a

def main():
	t = inin()
	for _ in range(t):
		(n, k) = cin()
		a = sin()
		l = ch('R', 'G', 'B', n)
		ans = 0
		an = 10000000000
		for i in range(k):
			if a[i] != l[i]:
				ans += 1
		an = min(ans, an)
		for i in range(k, n):
			if a[i] != l[i]:
				ans += 1
			if a[i - k] != l[i - k]:
				ans -= 1
			an = min(ans, an)
		l = ch('G', 'B', 'R', n)
		ans = 0
		for i in range(k):
			if a[i] != l[i]:
				ans += 1
		an = min(ans, an)
		for i in range(k, n):
			if a[i] != l[i]:
				ans += 1
			if a[i - k] != l[i - k]:
				ans -= 1
			an = min(ans, an)
		l = ch('B', 'R', 'G', n)
		ans = 0
		for i in range(k):
			if a[i] != l[i]:
				ans += 1
		an = min(ans, an)
		for i in range(k, n):
			if a[i] != l[i]:
				ans += 1
			if a[i - k] != l[i - k]:
				ans -= 1
			an = min(ans, an)
		print(an)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


from itertools import chain
from sys import stdin, stdout

def main():
	input = stdin.readline
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		ans = [k, k, k, 1, 1]
		fin_ans = k
		inp = tuple(((ord('r') + i - ord(c)) % 3 for (i, c) in enumerate(input().rstrip().lower())))
		for (inp1, inp2) in zip(inp, chain((4,) * k, inp)):
			ans[inp2] += 1
			ans[inp1] -= 1
			fin_ans = min(fin_ans, ans[inp1])
		stdout.write(f'{fin_ans}\n')
main()


x = int(input())
y = []

def kukareku(st, k):
	ans0 = 0
	ans1 = 0
	ans2 = 0
	a = 1
	sp = []
	spans = []
	for i in range(0, len(st)):
		f = []
		if i % 3 == 0:
			if st[i] == 'R':
				f = [0, 1, 1]
			elif st[i] == 'G':
				f = [1, 0, 1]
			else:
				f = [1, 1, 0]
		elif i % 3 == 1:
			if st[i] == 'G':
				f = [0, 1, 1]
			elif st[i] == 'B':
				f = [1, 0, 1]
			else:
				f = [1, 1, 0]
		elif st[i] == 'B':
			f = [0, 1, 1]
		elif st[i] == 'R':
			f = [1, 0, 1]
		else:
			f = [1, 1, 0]
		sp.append(f)
		if a <= k:
			a += 1
			ans0 += sp[i][0]
			ans1 += sp[i][1]
			ans2 += sp[i][2]
		else:
			ans0 += sp[i][0]
			ans1 += sp[i][1]
			ans2 += sp[i][2]
			ans0 -= sp[i - k][0]
			ans1 -= sp[i - k][1]
			ans2 -= sp[i - k][2]
		if a > k:
			spans.append(min(ans0, ans1, ans2))
	return min(spans)
for i in range(0, x):
	(n, k) = input().split()
	k = int(k)
	st = input()
	x = kukareku(st, k)
	y.append(x)
for i in y:
	print(i)


from sys import stdin, stdout
import collections
Q = int(input())
ans = [0] * Q
for q in range(Q):
	(N, K) = [int(x) for x in stdin.readline().split()]
	s = input()
	res = N + 1
	if N == 1 or K == 1:
		ans[q] = 0
		continue
	prefix = [0] * (N + 1)
	for k in range(3):
		if k == 0:
			RGB = 'RGB'
		if k == 1:
			RGB = 'GBR'
		if k == 2:
			RGB = 'BRG'
		ssum = 0
		for i in range(N):
			letter = RGB[i % 3]
			if s[i] != letter:
				ssum += 1
			prefix[i + 1] = ssum
			if i >= K - 1:
				res = min(res, prefix[i + 1] - prefix[i + 1 - K])
	ans[q] = res
print(*ans, sep='\n')


from sys import stdin
t = int(input())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline()
	one = 'RGB' * (n // 3)
	s1 = 'RGB'
	one = one + s1[:n % 3]
	two = 'GBR' * (n // 3)
	s2 = 'GBR'
	two = two + s2[:n % 3]
	s3 = 'BRG'
	three = s3 * (n // 3)
	three = three + s3[:n % 3]
	(i, j) = (0, 0)
	(count1, count2, count3, m) = (0, 0, 0, n)
	while j < n:
		while j - i < k:
			if s[j] != one[j]:
				count1 += 1
			if s[j] != two[j]:
				count2 += 1
			if s[j] != three[j]:
				count3 += 1
			j += 1
		m = min(count1, count2, count3, m)
		if s[i] != one[i]:
			count1 -= 1
		if s[i] != two[i]:
			count2 -= 1
		if s[i] != three[i]:
			count3 -= 1
		i += 1
	print(m)


from sys import stdin, stdout
input = stdin.readline
d1 = ['R', 'G', 'B']
d2 = ['G', 'B', 'R']
d3 = ['B', 'R', 'G']
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	ans = float('inf')
	temp = s[0:k]
	a = b = c = 0
	p = 0
	q = 1
	r = 2
	for j in temp:
		if j != d1[p]:
			a += 1
		if j != d1[q]:
			b += 1
		if j != d1[r]:
			c += 1
		p += 1
		p %= 3
		q += 1
		q %= 3
		r += 1
		r %= 3
	ans = min(a, b, c)
	for i in range(1, n - k + 1):
		first = i
		last = i + k - 1
		if s[first - 1] != d1[0]:
			a -= 1
		if s[first - 1] != d2[0]:
			b -= 1
		if s[first - 1] != d3[0]:
			c -= 1
		(a, b, c) = (c, a, b)
		if s[last] != d1[(k - 1) % 3]:
			a += 1
		if s[last] != d2[(k - 1) % 3]:
			b += 1
		if s[last] != d3[(k - 1) % 3]:
			c += 1
		ans = min(ans, a, b, c)
	print(ans)


import sys
input = sys.stdin.readline

def main():
	Q = int(input())
	data = []
	for _ in range(Q):
		(N, K) = map(int, input().split())
		S = input().rstrip()
		data.append([N, K, S])
	RGB = []
	for i in range(300000):
		if i % 3 == 0:
			RGB.append('R')
		elif i % 3 == 1:
			RGB.append('G')
		else:
			RGB.append('B')
	for (N, K, S) in data:
		ans = N
		dp = [[0 for _ in range(N)] for _ in range(3)]
		for j in range(3):
			for i in range(N):
				if S[i] != RGB[i + j]:
					dp[j][i] = 1
		for j in range(3):
			p = 0
			for k in range(K):
				p += dp[j][k]
			ans = min(ans, p)
			for i in range(1, N - K + 1):
				p += dp[j][K - 1 + i] - dp[j][i - 1]
				ans = min(ans, p)
		print(ans)
main()


q = int(input())
rgb = 'RGB'
answer = []
for req in range(q):
	(n, k) = map(int, input().split())
	s = input()
	last1 = rgb[(k - 1) % 3]
	last2 = rgb[k % 3]
	last3 = rgb[(k + 1) % 3]
	dp = [0, 0, 0]
	for i in range(k):
		if s[i] != rgb[i % 3]:
			dp[0] += 1
		if s[i] != rgb[(i + 1) % 3]:
			dp[1] += 1
		if s[i] != rgb[(i + 2) % 3]:
			dp[2] += 1
	count = min(dp)
	for i in range(k, n):
		first = s[i - k]
		if first != 'R':
			dp[0] -= 1
		if first != 'G':
			dp[1] -= 1
		if first != 'B':
			dp[2] -= 1
		dp.insert(0, dp.pop())
		last = s[i]
		if last != last1:
			dp[0] += 1
		if last != last2:
			dp[1] += 1
		if last != last3:
			dp[2] += 1
		count = min(min(dp), count)
	answer.append(str(count))
print('\n'.join(answer))


import sys
for _ in range(int(sys.stdin.readline())):
	(n, k) = [int(i) for i in sys.stdin.readline().split()]
	word = sys.stdin.readline().strip()
	ans = 0
	for col in ['RGB', 'GBR', 'BRG']:
		cnt = 0
		for i in range(k):
			if word[i] == col[i % 3]:
				cnt += 1
		mx = cnt
		for i in range(n - k):
			if word[i + k] == col[(i + k) % 3]:
				cnt += 1
			if word[i] == col[i % 3]:
				cnt -= 1
			if cnt > mx:
				mx = cnt
		ans = max(ans, mx)
	sys.stdout.write(str(k - ans) + '\n')


from __future__ import division, print_function

def main():
	t = int(input())
	s1 = 'RGB'
	s2 = 'BRG'
	s3 = 'GBR'
	for test_case in range(t):
		(n, k) = map(int, input().split())
		s = input()
		ans = 1000000000.0
		diff = [0] * n
		cur = 0
		for i in range(n):
			if s[i] != s1[i % 3]:
				diff[i] = 1
			cur += diff[i]
			if i >= k:
				cur -= diff[i - k]
			if i >= k - 1:
				ans = min(ans, cur)
		diff = [0] * n
		cur = 0
		for i in range(n):
			if s[i] != s2[i % 3]:
				diff[i] = 1
			cur += diff[i]
			if i >= k:
				cur -= diff[i - k]
			if i >= k - 1:
				ans = min(ans, cur)
		diff = [0] * n
		cur = 0
		for i in range(n):
			if s[i] != s3[i % 3]:
				diff[i] = 1
			cur += diff[i]
			if i >= k:
				cur -= diff[i - k]
			if i >= k - 1:
				ans = min(ans, cur)
		print(ans)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	for _ in range(N()):
		(n, k) = RL()
		s = input()
		rec = ['R', 'G', 'B']
		res = INF
		for i in range(3):
			sm = [0]
			x = i
			for j in range(n):
				if s[j] == rec[x % 3]:
					sm.append(sm[-1])
				else:
					sm.append(sm[-1] + 1)
				x = (x + 1) % 3
			for j in range(k, len(sm)):
				res = min(res, sm[j] - sm[j - k])
		print(res)
main()


from sys import stdin
input = stdin.readline
R = lambda : map(int, input().split())
(q,) = R()
a = 'RGB'
for q1 in range(q):
	an = [300000] * 3
	(n, k) = R()
	s = input()
	for i2 in range(3):
		ans = [0] * n
		m = 0
		for i in range(n):
			ans[i] = s[i] == a[(i + i2) % 3]
			m += ans[i] == 0
			if i >= k:
				m -= ans[i - k] == 0
			if i >= k - 1:
				an[i2] = min(an[i2], m)
	print(min(an))


import sys
input = sys.stdin.readline
Q = int(input())
D = {'R': 0, 'G': 1, 'B': 2}
for _ in range(Q):
	(N, K) = list(map(int, input().split()))
	S = input()
	mi = K
	for i in range(3):
		d = 0
		for j in range(N):
			if D[S[j]] != (i + j) % 3:
				d += 1
			if j >= K and D[S[j - K]] != (i + j - K) % 3:
				d -= 1
			if j >= K - 1:
				mi = min(mi, d)
	print(mi)


def solve():
	(l, k) = [int(i) for i in input().split(' ')]
	a = input()
	n = {'R': 'G', 'G': 'B', 'B': 'R'}
	x = 'R'
	y = 'G'
	z = 'B'
	prev_x = 'R'
	prev_y = 'G'
	prev_z = 'B'
	x_c = y_c = z_c = 0
	m = float('inf')
	for i in range(k):
		if a[i] != x:
			x_c += 1
		if a[i] != y:
			y_c += 1
		if a[i] != z:
			z_c += 1
		x = n[x]
		y = n[y]
		z = n[z]
	m = min(m, x_c, y_c, z_c)
	import code
	for i in range(k, l):
		import code
		if a[i - k] != prev_x:
			x_c -= 1
		if a[i - k] != prev_y:
			y_c -= 1
		if a[i - k] != prev_z:
			z_c -= 1
		if a[i] != x:
			x_c += 1
		if a[i] != y:
			y_c += 1
		if a[i] != z:
			z_c += 1
		prev_x = n[prev_x]
		prev_y = n[prev_y]
		prev_z = n[prev_z]
		x = n[x]
		y = n[y]
		z = n[z]
		import code
		m = min(m, x_c, y_c, z_c)
	return m
q = int(input())
o = ''
for _ in range(q):
	o += str(solve()) + '\n'
print(o)


q = int(input())
f = []
for i in range(q):
	(n, k) = map(int, input().split())
	s = input()
	mi = 0
	num = [0, 0, 0]
	for i in range(n):
		if i % 3 == 0:
			if s[i] == 'R':
				num[0] += 1
			elif s[i] == 'G':
				num[1] += 1
			else:
				num[2] += 1
		elif i % 3 == 1:
			if s[i] == 'G':
				num[0] += 1
			elif s[i] == 'B':
				num[1] += 1
			else:
				num[2] += 1
		elif s[i] == 'B':
			num[0] += 1
		elif s[i] == 'R':
			num[1] += 1
		else:
			num[2] += 1
		if i >= k:
			if (i - k) % 3 == 0:
				if s[i - k] == 'R':
					num[0] -= 1
				elif s[i - k] == 'G':
					num[1] -= 1
				else:
					num[2] -= 1
			elif (i - k) % 3 == 1:
				if s[i - k] == 'G':
					num[0] -= 1
				elif s[i - k] == 'B':
					num[1] -= 1
				else:
					num[2] -= 1
			elif s[i - k] == 'B':
				num[0] -= 1
			elif s[i - k] == 'R':
				num[1] -= 1
			else:
				num[2] -= 1
		e = max(num)
		if mi < e:
			mi = e
	f += [k - mi]
for i in f:
	print(i)


import sys
input = sys.stdin.readline
q = int(input())
rgb = 'RGB'
for _ in range(q):
	(n, k) = map(int, input().split())
	s = input()
	ans = n
	for i in range(3):
		r = [0]
		l = i
		for c in s:
			r.append(r[-1] + (1 if c != rgb[l] else 0))
			l = (l + 1) % 3
			if len(r) > k:
				ans = min(ans, r[-1] - r[len(r) - 1 - k])
	print(ans)


import sys
input = sys.stdin.readline
q = int(input())
for testcases in range(q):
	(n, k) = list(map(int, input().split()))
	S = list(input().strip())
	for i in range(n):
		if S[i] == 'R':
			S[i] = 0
		elif S[i] == 'G':
			S[i] = 1
		else:
			S[i] = 2
	ANS = 1 << 50
	for mod in range(3):
		SUM = 0
		for i in range(k):
			if S[i] % 3 != (mod + i) % 3:
				SUM += 1
		ANS = min(ANS, SUM)
		for i in range(k, n):
			if S[i - k] != (mod + (i - k)) % 3:
				SUM -= 1
			if S[i] != (mod + i) % 3:
				SUM += 1
			ANS = min(ANS, SUM)
	print(ANS)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque

def conv(let):
	if let == 'R':
		return 0
	elif let == 'G':
		return 1
	else:
		return 2
for j in range(int(input())):
	(n, k) = map(int, input().split())
	vals = [conv(i) for i in input()]
	store = [[0, (k - 1) % 3], [1, k % 3], [2, (k + 1) % 3]]
	cost = [0, 0, 0]
	mincost = 10 ** 9
	for s in range(3):
		for i in range(k):
			if vals[i] != (s + i) % 3:
				cost[s] += 1
	mincost = min(cost)
	for i in range(1, n + 1 - k):
		for s in range(3):
			if vals[i - 1] != store[s][0]:
				cost[s] -= 1
			store[s][0] += 1
			store[s][1] += 1
			store[s][0] = store[s][0] % 3
			store[s][1] = store[s][1] % 3
			if vals[i + k - 1] != store[s][1]:
				cost[s] += 1
		mincost = min(mincost, min(cost))
	print(mincost)


import sys
input = sys.stdin.readline
rgb = ['R', 'G', 'B']

def func(s):
	r = [0, 0, 0]
	i = 0
	for c in s:
		if c == rgb[i]:
			r[1] += 1
			r[2] += 1
		elif c == rgb[(i + 1) % 3]:
			r[2] += 1
			r[0] += 1
		else:
			r[0] += 1
			r[1] += 1
		i = (i + 1) % 3
	return r
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	dp = func(s[:k])
	ans = min(dp)
	(x, y, z) = ((k - 1 + 3) % 3, 0, 1)
	for i in range(k, n):
		for j in range(3):
			if s[i - k] != rgb[y]:
				dp[j] -= 1
			y = (y + 1) % 3
		(dp[1], dp[2], dp[0]) = (dp[0], dp[1], dp[2])
		for j in range(3):
			if s[i] != rgb[x]:
				dp[j] += 1
			x = (x + 1) % 3
		ans = min(ans, min(dp))
	print(ans)


temp = ''
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	r = 'RGB' * (n // 3) + 'RGB'[:n % 3]
	g = 'GBR' * (n // 3) + 'GBR'[:n % 3]
	b = 'BRG' * (n // 3) + 'BRG'[:n % 3]
	ra = []
	ga = []
	ba = []
	for i in range(n):
		if r[i] == s[i]:
			ra.append(0)
		elif r[i] != s[i]:
			ra.append(1)
		if g[i] == s[i]:
			ga.append(0)
		elif g[i] != s[i]:
			ga.append(1)
		if b[i] == s[i]:
			ba.append(0)
		elif b[i] != s[i]:
			ba.append(1)
	pre_r = [0, ra[0]]
	pre_g = [0, ga[0]]
	pre_b = [0, ba[0]]
	ans = float('INF')
	for i in range(1, n):
		pre_r.append(pre_r[i] + ra[i])
		pre_g.append(pre_g[i] + ga[i])
		pre_b.append(pre_b[i] + ba[i])
	for i in range(k, n + 1):
		ans = min(ans, pre_r[i] - pre_r[i - k], pre_g[i] - pre_g[i - k], pre_b[i] - pre_b[i - k])
	temp += str(ans) + '\n'
print(temp)


import math as mt
import sys, string
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
a = 'RGB'
b = 'GBR'
c = 'BRG'
t = I()
for _ in range(t):
	(n, k) = M()
	s = input()
	ac = 0
	bc = 0
	cc = 0
	for i in range(k):
		if a[i % 3] != s[i]:
			ac += 1
		if b[i % 3] != s[i]:
			bc += 1
		if c[i % 3] != s[i]:
			cc += 1
	aes = ac
	bs = bc
	cs = cc
	for i in range(k, n):
		ac += int(not a[i % 3] == s[i])
		ac -= int(not a[(i - k) % 3] == s[i - k])
		aes = min(aes, ac)
		bc += int(not b[i % 3] == s[i])
		bc -= int(not b[(i - k) % 3] == s[i - k])
		bs = min(bs, bc)
		cc += int(not c[i % 3] == s[i])
		cc -= int(not c[(i - k) % 3] == s[i - k])
		cs = min(cs, cc)
	print(min(aes, bs, cs))


from sys import stdin
q = int(input())
INF = 10 ** 18
for _ in range(q):
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline()[:-1]
	r = ('RGB' * k)[:k]
	g = ('GBR' * k)[:k]
	b = ('BRG' * k)[:k]
	dp = [[0] * 3 for i in range(n)]
	for i in range(k):
		if s[i] == r[i]:
			dp[k - 1][0] += 1
		elif s[i] == g[i]:
			dp[k - 1][1] += 1
		elif s[i] == b[i]:
			dp[k - 1][2] += 1
	ans = max(dp[k - 1])
	for i in range(k, n):
		dp[i][0] = dp[i - 1][2] - (s[i - k] == b[0]) + (s[i] == r[k - 1])
		dp[i][1] = dp[i - 1][0] - (s[i - k] == r[0]) + (s[i] == g[k - 1])
		dp[i][2] = dp[i - 1][1] - (s[i - k] == g[0]) + (s[i] == b[k - 1])
		ans = max(ans, max(dp[i]))
	print(k - ans)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = I()
	s = input()
	an = k
	rq = 'RGB'
	for j in range(3):
		cr = 0
		for i in range(k):
			if s[i] != rq[(j + i) % 3]:
				cr += 1
		an = min(cr, an)
		for i in range(k, n):
			if s[i - k] != rq[(j + i - k) % 3]:
				cr -= 1
			if s[i] != rq[(j + i) % 3]:
				cr += 1
			an = min(cr, an)
	print(an)


from sys import stdin
import math
rgb = 'RGB'
for query in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline()
	ans = math.inf
	for start in range(3):
		dp = [0 for i in range(n + 1)]
		for i in range(n):
			cur = rgb[(start + i) % len(rgb)]
			dp[i + 1] = dp[i] + int(s[i] != cur)
		for i in range(n - k + 1):
			ans = min(ans, dp[i + k] - dp[i])
	print(ans)


from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	x = 10 ** 5
	(n, k) = list(map(int, input().split()))
	s = input()
	a = 10 ** 9
	ans = [[0] * n for i in range(3)]
	curr = ['R', 'G', 'B']
	for l in range(3):
		z = l
		for j in range(n):
			if s[j] != curr[z]:
				ans[l][j] = 1
			z += 1
			z %= 3
	for i in range(3):
		ans[i] = [0] + ans[i]
	for l in range(3):
		z = l
		for j in range(1, n + 1):
			ans[l][j] += ans[l][j - 1]
	for l in range(3):
		for j in range(1, n - k + 2):
			a = min(a, ans[l][j + k - 1] - ans[l][j - 1])
	print(a)


from sys import stdin, stdout

def check(s, k, n):
	t = 'RGB'
	ans = int(1000000000.0)
	for off in range(0, 3):
		res = [None] * n
		curr = 0
		for j in range(n):
			res[j] = s[j] != t[(j + off) % 3]
			curr += res[j]
			if j >= k:
				curr -= res[j - k]
			if j >= k - 1:
				ans = min(ans, curr)
	return ans
t = int(stdin.readline())
while t:
	nk = list(map(int, stdin.readline().rstrip().split()))
	n = nk[0]
	k = nk[1]
	s = stdin.readline().rstrip().lstrip()
	stdout.write(str(check(s, k, n)) + '\n')
	t = t - 1


import sys
input = sys.stdin.readline
q = int(input())
d = {'R': 0, 'G': 1, 'B': 2}
for _ in range(q):
	(n, k) = map(int, input().split())
	s = list(input().rstrip())
	for i in range(n):
		s[i] = d[s[i]]
	t = [(s[i] - i) % 3 for i in range(n)]
	cnt = [0] * 3
	for i in range(k):
		cnt[t[i]] += 1
	ans = k - max(cnt)
	for i in range(n - k):
		cnt[t[i]] -= 1
		cnt[t[i + k]] += 1
		ans = min(ans, k - max(cnt))
	print(ans)


import sys
input = sys.stdin.readline
q = int(input())
for i in range(q):
	(n, k) = map(int, input().split())
	s = input()
	(R, G, B) = (0, 0, 0)
	ans = float('inf')
	for j in range(n):
		if j % 3 == 0:
			if s[j] == 'R':
				G += 1
				B += 1
			elif s[j] == 'G':
				R += 1
				B += 1
			else:
				R += 1
				G += 1
		elif j % 3 == 1:
			if s[j] == 'R':
				G += 1
				R += 1
			elif s[j] == 'G':
				G += 1
				B += 1
			else:
				R += 1
				B += 1
		elif s[j] == 'R':
			R += 1
			B += 1
		elif s[j] == 'G':
			R += 1
			G += 1
		else:
			G += 1
			B += 1
		if j >= k - 1:
			ans = min(ans, R, G, B)
			if (j - k + 1) % 3 == 0:
				if s[j - k + 1] == 'R':
					G -= 1
					B -= 1
				elif s[j - k + 1] == 'G':
					R -= 1
					B -= 1
				else:
					R -= 1
					G -= 1
			elif (j - k + 1) % 3 == 1:
				if s[j - k + 1] == 'R':
					G -= 1
					R -= 1
				elif s[j - k + 1] == 'G':
					G -= 1
					B -= 1
				else:
					R -= 1
					B -= 1
			elif s[j - k + 1] == 'R':
				R -= 1
				B -= 1
			elif s[j - k + 1] == 'G':
				R -= 1
				G -= 1
			else:
				G -= 1
				B -= 1
	print(ans)


import sys
from math import log2
import bisect
import heapq
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
for _ in range(int(ri())):
	(n, k) = Ri()
	st = ri()
	B = 'BRG' * (k // 3 + 2)
	R = 'RGB' * (k // 3 + 2)
	G = 'GBR' * (k // 3 + 2)
	dpb = [0] * n
	dpr = [0] * n
	dpg = [0] * n
	cnt = 0
	for i in range(k):
		if st[i] != B[i]:
			cnt += 1
	dpb[k - 1] = cnt
	cnt = 0
	for i in range(k):
		if st[i] != G[i]:
			cnt += 1
	dpg[k - 1] = cnt
	cnt = 0
	for i in range(k):
		if st[i] != R[i]:
			cnt += 1
	dpr[k - 1] = cnt
	for i in range(k, n):
		dpb[i] = dpg[i - 1] + (1 if B[k - 1] != st[i] else 0)
		if st[i - k] != 'G':
			dpb[i] -= 1
		dpr[i] = dpb[i - 1] + (1 if R[k - 1] != st[i] else 0)
		if st[i - k] != 'B':
			dpr[i] -= 1
		dpg[i] = dpr[i - 1] + (1 if G[k - 1] != st[i] else 0)
		if st[i - k] != 'R':
			dpg[i] -= 1
	minn = INF
	for i in range(k - 1, n):
		minn = min(minn, dpb[i], dpg[i], dpr[i])
	print(minn)


def int_list():
	return [int(c) for c in input().split()]

def int1():
	return int(input())

def str_list():
	return [c for c in input().split()]

def str1():
	return input()
s1 = ('RGB' * 66667)[:-1]
s2 = ('GBR' * 66667)[:-1]
s3 = ('BRG' * 66667)[:-1]
q = int1()
res = []
for j in range(q):
	(n, k) = int_list()
	s = str1()
	c1 = []
	c2 = []
	c3 = []
	for i in range(n):
		if s[i] != s1[i]:
			c1.append(1)
		else:
			c1.append(0)
		if s[i] != s2[i]:
			c2.append(1)
		else:
			c2.append(0)
		if s[i] != s3[i]:
			c3.append(1)
		else:
			c3.append(0)
	min1 = sum(c1[:k])
	min2 = sum(c2[:k])
	min3 = sum(c3[:k])
	cost1 = min1
	cost2 = min2
	cost3 = min3
	for i in range(k, n):
		cost1 += c1[i] - c1[i - k]
		cost2 += c2[i] - c2[i - k]
		cost3 += c3[i] - c3[i - k]
		min1 = cost1 if cost1 < min1 else min1
		min2 = cost2 if cost2 < min2 else min2
		min3 = cost3 if cost3 < min3 else min3
	res.append(min(min1, min2, min3))
for result in res:
	print(result)


from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	s1 = 'RGB'
	s2 = 'GBR'
	s3 = 'BRG'
	ans = 200000
	(cnt1, cnt2, cnt3) = (0, 0, 0)
	dp = [[0 for i in range(3)] for j in range(n + 1)]
	dp[0][0] = 0
	dp[0][1] = 0
	dp[0][2] = 0
	for i in range(n):
		if s[i] != s1[i % 3]:
			cnt1 += 1
		if s[i] != s2[i % 3]:
			cnt2 += 1
		if s[i] != s3[i % 3]:
			cnt3 += 1
		dp[i + 1][0] = cnt1
		dp[i + 1][1] = cnt2
		dp[i + 1][2] = cnt3
	for i in range(k, n + 1):
		ans = min(ans, dp[i][0] - dp[i - k][0], dp[i][1] - dp[i - k][1], dp[i][2] - dp[i - k][2])
	print(ans)


import sys
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	s = sys.stdin.readline()
	d = {}
	d['R'] = [0, 0, 0]
	d['G'] = [0, 0, 0]
	d['B'] = [0, 0, 0]
	res = 0
	for i in range(k):
		d[s[i]][i % 3] += 1
	res = max(d['R'][0] + d['G'][1] + d['B'][2], d['R'][1] + d['G'][2] + d['B'][0], d['R'][2] + d['G'][0] + d['B'][1])
	for i in range(k, n):
		d[s[i]][i % 3] += 1
		d[s[i - k]][(i - k) % 3] -= 1
		res = max(res, d['R'][0] + d['G'][1] + d['B'][2], d['R'][1] + d['G'][2] + d['B'][0], d['R'][2] + d['G'][0] + d['B'][1])
		if res >= k:
			break
	print(k - res)


import sys
input = sys.stdin.readline
RI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
rw = lambda : input().strip().split()
infinite = float('inf')
t = int(input())
for _ in range(t):
	(n, k) = RI()
	s = input()
	mini = n
	count = 0
	test = 'RGB' * (k // 3 + 5)
	for j in range(k):
		if s[j] != test[j]:
			count += 1
	mini = min(count, mini)
	count1 = count
	count = 0
	test = 'GBR' * (k // 3 + 5)
	for j in range(k):
		if s[j] != test[j]:
			count += 1
	mini = min(count, mini)
	count2 = count
	count = 0
	test = 'BRG' * (k // 3 + 5)
	for j in range(k):
		if s[j] != test[j]:
			count += 1
	mini = min(count, mini)
	count3 = count
	count = 0
	for i in range(1, n - k + 1):
		if s[i - 1] == 'B':
			count = count3
			temp = 'RGB' * (k // 3 + 5)
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count1_new = count
			count = count1 - 1
			temp = 'GBR' * (k // 3 + 5)
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count2_new = count
			temp = 'BRG' * (k // 3 + 5)
			count = count2 - 1
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count3_new = count
			count1 = count1_new
			count2 = count2_new
			count3 = count3_new
		elif s[i - 1] == 'R':
			temp = 'GBR' * (k // 3 + 5)
			count = count1
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count2_new = count
			temp = 'BRG' * (k // 3 + 5)
			count = count2 - 1
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count3_new = count
			temp = 'RGB' * (k // 3 + 5)
			count = count3 - 1
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count1_new = count
			count1 = count1_new
			count2 = count2_new
			count3 = count3_new
		else:
			count = count2
			temp = 'BRG' * (k // 3 + 5)
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count3_new = count
			temp = 'RGB' * (k // 3 + 5)
			count = count3 - 1
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count1_new = count
			temp = 'GBR' * (k // 3 + 5)
			count = count1 - 1
			if s[i + k - 1] != temp[k - 1]:
				count += 1
			mini = min(count, mini)
			count2_new = count
			count1 = count1_new
			count2 = count2_new
			count3 = count3_new
	print(mini)


import os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(input())

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

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

def Sn():
	return input().strip()
BUFSIZE = 8192

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def solve():
	d = {'R': 0, 'G': 1, 'B': 2}

	def get(ch, le):
		t = (d[ch] + le) % 3
		return t
	(n, k) = In()
	s = Sn()
	dp = [[0, 0, 0]]
	for i in range(n):
		dp.append([0, 0, 0])
		if s[i] == 'R':
			dp[i + 1][0] = dp[i][2]
			dp[i + 1][1] = dp[i][0] + 1
			dp[i + 1][2] = dp[i][1] + 1
		elif s[i] == 'G':
			dp[i + 1][0] = dp[i][2] + 1
			dp[i + 1][1] = dp[i][0]
			dp[i + 1][2] = dp[i][1] + 1
		else:
			dp[i + 1][0] = dp[i][2] + 1
			dp[i + 1][1] = dp[i][0] + 1
			dp[i + 1][2] = dp[i][1]
	ans = float('inf')
	for i in range(1, n - k + 2):
		tr = dp[i + k - 1][get('R', k - 1)] - dp[i][0]
		tg = dp[i + k - 1][get('G', k - 1)] - dp[i][1]
		tb = dp[i + k - 1][get('B', k - 1)] - dp[i][2]
		if s[i - 1] == 'R':
			tb += 1
			tg += 1
		elif s[i - 1] == 'G':
			(tr, tb) = (tr + 1, tb + 1)
		else:
			(tr, tg) = (tr + 1, tg + 1)
		ans = min(tr, tg, tb, ans)
	print(ans)
	pass

def main():
	T = I()
	for i in range(T):
		solve()
M = 998244353
P = 1000000007

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, stdout
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warmup = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7
import sys

class merge_find:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def primeFactors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def isprime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warmup
	if fac_warmup:
		return
	factorial_modP = [1 for _ in range(fac_warmup_size + 1)]
	for i in range(2, fac_warmup_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warmup = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warmup, factorial_modP
	if not fac_warmup:
		warm_up_fac(MOD)
		fac_warmup = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def test_print(*args):
	if testingMode:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def display_2D_list(li):
	for i in li:
		print(i)

def prefix_sum(li):
	sm = 0
	res = []
	for i in li:
		sm += i
		res.append(sm)
	return res

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
import heapq, itertools
pq = []
entry_finder = {}
REMOVED = '<removed-task>'

def add_task(task, priority=0):
	if task in entry_finder:
		remove_task(task)
	count = next(counter)
	entry = [priority, count, task]
	entry_finder[task] = entry
	heapq.heappush(pq, entry)

def remove_task(task):
	entry = entry_finder.pop(task)
	entry[-1] = REMOVED

def pop_task():
	while pq:
		(priority, count, task) = heapq.heappop(pq)
		if task is not REMOVED:
			del entry_finder[task]
			return task
	raise KeyError('pop from an empty priority queue')
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_serach(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
testingMode = False
fac_warmup_size = 10 ** 5 + 100
optimiseForReccursion = False
from math import factorial

def main():
	(n, k) = get_tuple()
	st = stdin.readline()
	li = ['R', 'G', 'B']
	for offset in range(3):
		cnt = 0
		for i in range(k):
			if st[i] != li[(i + offset) % 3]:
				cnt += 1
		if offset == 0:
			min_cnt = cnt
		min_cnt = min(min_cnt, cnt)
		for i in range(k, n):
			if st[i - k] != li[(i - k + offset) % 3]:
				cnt -= 1
			if st[i] != li[(i + offset) % 3]:
				cnt += 1
			min_cnt = min(min_cnt, cnt)
	print(min_cnt)
if TestCases:
	for i in range(get_int()):
		cProfile.run('main()') if testingMode else main()
else:
	(cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()


from sys import stdin, stdout
from collections import Counter
import math

def rsingle_int():
	return int(stdin.readline().rstrip())

def rmult_int():
	return [int(x) for x in stdin.readline().rstrip().split()]

def rmult_str():
	return stdin.readline().rstrip().split()

def r_str():
	return stdin.readline().rstrip()

def rsingle_char():
	return stdin.read(1)
rgbs = {'R': 'RGB', 'G': 'GBR', 'B': 'BRG'}

def create_rgb(start, k):
	temp = rgbs[start]
	return temp * (k // 3) + temp[:k % 3]

def main():
	q = rsingle_int()
	rgb = 'RGB'
	for i in range(q):
		(n, k) = rmult_int()
		s = r_str()
		all_min = k
		for shift in range(3):
			rgb_temp = create_rgb(rgb[shift], n)
			diff = []
			for i in range(n):
				if s[i] == rgb_temp[i]:
					diff.append(0)
				else:
					diff.append(1)
			min = 0
			for i in range(n):
				min += diff[i]
				if i >= k:
					min -= diff[i - k]
				if i >= k - 1:
					if all_min > min:
						all_min = min
		print(all_min)
main()


def RGBstring(s, n, k):
	if n == 1:
		return 0
	string = 'RGB' * n
	s1 = string[0:n]
	s2 = string[1:n + 1]
	s3 = string[2:n + 2]
	(arr1, arr2, arr3) = ([], [], [])
	for i in range(n):
		if s[i] != s1[i]:
			arr1.append(1)
		else:
			arr1.append(0)
		if s[i] != s2[i]:
			arr2.append(1)
		else:
			arr2.append(0)
		if s[i] != s3[i]:
			arr3.append(1)
		else:
			arr3.append(0)
	temp = arr1[0]
	prefix1 = [temp]
	for i in range(1, n):
		temp = temp + arr1[i]
		prefix1.append(temp)
	temp = arr2[0]
	prefix2 = [temp]
	for i in range(1, n):
		temp = temp + arr2[i]
		prefix2.append(temp)
	temp = arr3[0]
	prefix3 = [temp]
	for i in range(1, n):
		temp = temp + arr3[i]
		prefix3.append(temp)
	res = n
	for i in range(k - 1, n):
		if i == k - 1:
			res = min(res, prefix1[i], prefix2[i], prefix3[i])
		else:
			res = min(res, prefix1[i] - prefix1[i - k], prefix2[i] - prefix2[i - k], prefix3[i] - prefix3[i - k])
	return res
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(RGBstring(s, n, k))


def change(d):
	for i in range(0, len(d)):
		if d[i] == 'R':
			d[i] = 1
		elif d[i] == 'G':
			d[i] = 2
		else:
			d[i] = 3
	return d
a = int(input())
if a < 100000:
	for i in range(0, a):
		(n, k) = map(int, input().split())
		c = list(input())
		c = change(c)
		e = 0
		f = 0
		g = 0
		h = [0] * (3 * (n - k + 1))
		mod3 = [0] * n
		for i in range(0, n):
			mod3[i] = (c[i] - i) % 3
		for i in range(0, k):
			if mod3[i] == 0:
				h[0] = h[0] + 1
			elif mod3[i] == 1:
				h[1] = h[1] + 1
			elif mod3[i] == 2:
				h[2] = h[2] + 1
		for i in range(0, n - k):
			if mod3[i] == 1:
				if mod3[i + k] == 1:
					h[3 * (i + 1)] = h[3 * i]
					h[3 * (i + 1) + 1] = h[3 * i + 1]
					h[3 * (i + 1) + 2] = h[3 * i + 2]
				elif mod3[i + k] == 2:
					h[3 * (i + 1)] = h[3 * i]
					h[3 * (i + 1) + 1] = h[3 * i + 1] - 1
					h[3 * (i + 1) + 2] = h[3 * i + 2] + 1
				elif mod3[i + k] == 0:
					h[3 * (i + 1)] = h[3 * i] + 1
					h[3 * (i + 1) + 1] = h[3 * i + 1] - 1
					h[3 * (i + 1) + 2] = h[3 * i + 2]
			elif mod3[i] == 2:
				if mod3[i + k] == 1:
					h[3 * (i + 1)] = h[3 * i]
					h[3 * (i + 1) + 1] = h[3 * i + 1] + 1
					h[3 * (i + 1) + 2] = h[3 * i + 2] - 1
				elif mod3[i + k] == 2:
					h[3 * (i + 1)] = h[3 * i]
					h[3 * (i + 1) + 1] = h[3 * i + 1]
					h[3 * (i + 1) + 2] = h[3 * i + 2]
				elif mod3[i + k] == 0:
					h[3 * (i + 1)] = h[3 * i] + 1
					h[3 * (i + 1) + 1] = h[3 * i + 1]
					h[3 * (i + 1) + 2] = h[3 * i + 2] - 1
			elif mod3[i] == 0:
				if mod3[i + k] == 1:
					h[3 * (i + 1)] = h[3 * i] - 1
					h[3 * (i + 1) + 1] = h[3 * i + 1] + 1
					h[3 * (i + 1) + 2] = h[3 * i + 2]
				elif mod3[i + k] == 2:
					h[3 * (i + 1)] = h[3 * i] - 1
					h[3 * (i + 1) + 1] = h[3 * i + 1]
					h[3 * (i + 1) + 2] = h[3 * i + 2] + 1
				elif mod3[i + k] == 0:
					h[3 * (i + 1)] = h[3 * i]
					h[3 * (i + 1) + 1] = h[3 * i + 1]
					h[3 * (i + 1) + 2] = h[3 * i + 2]
		print(k - max(h))
elif a == 100000:
	for i in range(0, a):
		(n, k) = map(int, input().split())
		c = list(input())
		e = 0
		if k == 1:
			print(0)
		elif n > 2:
			e = [0] * (3 * (n - k + 1))
			c = change(c)
			for i in range(0, n - k + 1):
				for j in range(i, i + k):
					if (c[j] - c[i]) % 3 != (j - i) % 3:
						e[3 * i] = e[3 * i] + 1
					if (c[j] - c[i]) % 3 != (j - i - 1) % 3:
						e[3 * i + 1] = e[3 * i + 1] + 1
					if (c[j] - c[i]) % 3 != (j - i - 2) % 3:
						e[3 * i + 2] = e[3 * i + 2] + 1
			e.sort()
			print(e[0])
		else:
			c = change(c)
			if c[0] == 1:
				if c[1] == 2:
					print(0)
				else:
					print(1)
			elif c[0] == 2:
				if c[1] == 3:
					print(0)
				else:
					print(1)
			elif c[0] == 3:
				if c[1] == 1:
					print(0)
				else:
					print(1)
else:
	for i in range(0, a):
		print(0)


import sys
input = sys.stdin.readline
for _ in range(int(input().strip())):
	(n, k) = list(map(int, input().strip().split()))
	inp = input().strip()
	st = 'RGB'
	ans = float('inf')
	for offset in range(3):
		cur = 0
		pre = []
		for i in range(n):
			if inp[i] != st[(i + offset) % 3]:
				cur += 1
			pre.append(cur)
		for i in range(k - 1, n):
			if i == k - 1:
				ans = min(ans, pre[k - 1])
			else:
				ans = min(ans, pre[i] - pre[i - k])
	print(ans)


from sys import stdin
input = stdin.readline
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	str_1 = input()
	str_2 = ['GBR', 'BRG', 'RGB']
	do = []
	for h in str_2:
		count = 0
		for j in range(k):
			if str_1[j] != h[j % 3]:
				count += 1
		do.append(count)
		for j in range(k, n):
			if str_1[j - k] != h[(j - k) % 3]:
				count -= 1
			if str_1[j] != h[j % 3]:
				count += 1
			do.append(count)
	print(min(do))


from sys import stdin
input = stdin.readline
test = 'RGB'
for i in range(int(input())):
	(a, m) = map(int, input().split())
	s = input()
	f = 100000000
	ans = [[0] * a for i in range(3)]
	for i in range(3):
		for j in range(a):
			ans[i][j] += s[j] != test[(i + j) % 3]
	for i in range(3):
		mm = sum(ans[i][:m])
		f = min(f, mm)
		for j in range(m, a):
			mm -= ans[i][j - m]
			mm += ans[i][j]
			f = min(f, mm)
	print(f)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	if n == 1:
		print(0)
		continue
	A1 = 'RGB' * n
	A2 = 'GBR' * n
	A3 = 'BRG' * n
	ans = k
	x1 = 0
	x2 = 0
	x3 = 0
	for j in range(0, k):
		x1 += s[j] != A1[j]
		x2 += s[j] != A2[j]
		x3 += s[j] != A3[j]
	ans = min(ans, x1, x2, x3)
	for i in range(k, n):
		x1 += (s[i] != A1[i]) - (s[i - k] != A1[i - k])
		x2 += (s[i] != A2[i]) - (s[i - k] != A2[i - k])
		x3 += (s[i] != A3[i]) - (s[i - k] != A3[i - k])
		ans = min(ans, x1, x2, x3)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	s1 = 'RGB' * (n // 3 + 2)
	l1 = []
	l2 = []
	l3 = []
	(c1, c2, c3) = (0, 0, 0)
	for j in range(n):
		if s[j] == s1[j]:
			c1 += 1
		elif s[j] == s1[j + 1]:
			c2 += 1
		else:
			c3 += 1
		l1.append(c1)
		l2.append(c2)
		l3.append(c3)
	(a, b, c) = (l1[k - 1], l2[k - 1], l3[k - 1])
	ans = max(a, b, c)
	for j in range(k, n):
		a = max(a, l1[j] - l1[j - k])
		b = max(b, l2[j] - l2[j - k])
		c = max(c, l3[j] - l3[j - k])
		ans = max(ans, a, b, c)
	print(k - ans)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	a = sys.stdin.readline()
	b = 1
	c = [0] * 3
	a1 = 'RGB' * (n // 3 + 1)
	a1 = a1[:n]
	a2 = 'GBR' * (n // 3 + 1)
	a2 = a2[:n]
	a3 = 'BRG' * (n // 3 + 1)
	a3 = a3[:n]
	c1 = c2 = c3 = 0
	for i in range(m):
		if a[i] != a1[i]:
			c1 += 1
		if a[i] != a2[i]:
			c2 += 1
		if a[i] != a3[i]:
			c3 += 1
	c[0] = c1
	c[1] = c2
	c[2] = c3
	for i in range(m, n):
		if a[i] != a1[i]:
			c1 += 1
		if a[i] != a2[i]:
			c2 += 1
		if a[i] != a3[i]:
			c3 += 1
		if a[i - m] != a1[i - m]:
			c1 -= 1
		if a[i - m] != a2[i - m]:
			c2 -= 1
		if a[i - m] != a3[i - m]:
			c3 -= 1
		c[0] = min(c1, c[0])
		c[1] = min(c2, c[1])
		c[2] = min(c3, c[2])
	print(min(c))


from sys import stdin, stdout
import math, queue, heapq
fastinput = stdin.readline
fastout = stdout.write
t = int(fastinput())
re = []
while t:
	t -= 1
	(n, m) = map(int, fastinput().split())
	x = 'RGB'
	i = 0
	dp = [[0, 0, 0] for _ in range(n + 1)]
	j = 1
	s = input()
	ans = 0
	for k in s:
		if k == x[(i + 0) % 3]:
			dp[j][0] = 1
		elif k == x[(i + 1) % 3]:
			dp[j][1] = 1
		else:
			dp[j][2] = 1
		i = (i + 1) % 3
		dp[j][0] += dp[j - 1][0]
		dp[j][1] += dp[j - 1][1]
		dp[j][2] += dp[j - 1][2]
		if j >= m:
			ans = max(ans, dp[j][0] - dp[j - m][0], dp[j][1] - dp[j - m][1], dp[j][2] - dp[j - m][2])
		j += 1
	re.append(m - ans)
print(*re)


import sys
input = sys.stdin.readline
pure = 'RGB' * 100006
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	Rc = 0
	Gc = 0
	Bc = 0
	count = 0
	for i in range(k):
		if pure[i] == s[i]:
			Rc += 1
		elif pure[i - 1] == s[i]:
			Bc += 1
		elif pure[i - 2] == s[i]:
			Gc += 1
	ans = max(ans, Rc, Gc, Bc)
	for i in range(k, n):
		if pure[i] == s[i]:
			Rc += 1
		if pure[i - k] == s[i - k]:
			Rc -= 1
		if pure[i - 1] == s[i]:
			Bc += 1
		if pure[i - k - 1] == s[i - k]:
			Bc -= 1
		if pure[i - 2] == s[i]:
			Gc += 1
		if pure[i - k - 2] == s[i - k]:
			Gc -= 1
		ans = max(ans, Rc, Gc, Bc)
	print(k - ans)


import sys
quries = int(sys.stdin.readline())
result = []
mapping = {'R': 'G', 'G': 'B', 'B': 'R'}
rev_mapping = {'R': 'B', 'B': 'G', 'G': 'R'}
count = {'R': 0, 'B': 0, 'G': 0}
memory = {}
for i in range(quries):
	(n, k) = [int(x) for x in sys.stdin.readline().split()]
	best = 10000000
	lis = sys.stdin.readline()
	count = {'R': 0, 'B': 0, 'G': 0}
	for cur in ['R', 'G', 'B']:
		current = cur
		for s in range(0, k):
			if lis[s] != current:
				count[cur] += 1
			current = mapping[current]
	for (s, value) in count.items():
		best = min(best, value)
	for s in range(1, n - k + 1):
		count_temp = {'R': 0, 'G': 0, 'B': 0}
		for cur in ['R', 'G', 'B']:
			count_temp[cur] = count[rev_mapping[cur]]
			if lis[s - 1] != rev_mapping[cur]:
				count_temp[cur] -= 1
			needed = 'c'
			if k % 3 == 0:
				needed = mapping[mapping[cur]]
			elif k % 3 == 1:
				needed = cur
			else:
				needed = mapping[cur]
			if lis[s + k - 1] != needed:
				count_temp[cur] += 1
		count = count_temp
		for (s, value) in count.items():
			best = min(best, value)
	print(best, flush=False)


from heapq import heappush, heappop
from collections import deque, Counter, defaultdict
import itertools
import sys
sys.setrecursionlimit(10 ** 6)

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

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]
YN = ['YES', 'NO']
input = sys.stdin.readline
q = I()
for _ in range(q):
	(n, k) = LI()
	ans = k
	s = list(input())
	l = 'RGB'
	c = [[0], [0], [0]]
	for i in range(n):
		for j in range(3):
			if s[i] != l[(i + j) % 3]:
				c[j].append(c[j][-1] + 1)
			else:
				c[j].append(c[j][-1])
	for i in range(n - k + 1):
		for j in range(3):
			ans = min(c[j][i + k] - c[j][i], ans)
	print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(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
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
from decimal import *
from math import *

def solve():
	(n, k) = sep()
	s = inp()
	inf = float('inf')
	ar = [[0] * (n - k + 1) for _ in range(3)]
	temp = 'RGB'
	temp1 = []
	for i in range(n):
		if s[i] == temp[i % 3]:
			temp1.append(0)
		else:
			temp1.append(1)
	temp1.append(0)
	j = 0
	su = 0
	for i in range(k):
		su += temp1[i]
	for j in range(n - k + 1):
		ar[j % 3][j] = su
		su += temp1[k + j]
		su -= temp1[j]
	temp = 'GBR'
	temp1 = []
	for i in range(n):
		if s[i] == temp[i % 3]:
			temp1.append(0)
		else:
			temp1.append(1)
	temp1.append(0)
	su = 0
	for i in range(k):
		su += temp1[i]
	for j in range(n - k + 1):
		ar[(j + 1) % 3][j] = su
		su += temp1[k + j]
		su -= temp1[j]
	temp = 'BRG'
	temp1 = []
	for i in range(n):
		if s[i] == temp[i % 3]:
			temp1.append(0)
		else:
			temp1.append(1)
	temp1.append(0)
	su = 0
	for i in range(k):
		su += temp1[i]
	for j in range(n - k + 1):
		ar[(j + 2) % 3][j] = su
		su += temp1[k + j]
		su -= temp1[j]
	m = 9999999999999999
	for i in ar:
		m = min(m, min(i))
	print(m)
testcase(int(inp()))


from sys import stdin, stdout

def check_diff(s, rgb):
	n = len(s)
	arr = []
	for i in range(n):
		if s[i] == rgb[i]:
			arr.append(0)
		else:
			arr.append(1)
	return arr
q = int(stdin.readline().rstrip())
for _ in range(q):
	(n, k) = map(int, stdin.readline().rstrip().split())
	s = stdin.readline().rstrip()
	rgb = ('RGB' * n)[:n]
	gbr = ('GBR' * n)[:n]
	brg = ('BRG' * n)[:n]
	diff1 = check_diff(s, rgb)
	diff2 = check_diff(s, gbr)
	diff3 = check_diff(s, brg)
	cum1 = [0] * (n + 1)
	cum2 = [0] * (n + 1)
	cum3 = [0] * (n + 1)
	for i in range(1, n + 1):
		cum1[i] = cum1[i - 1] + diff1[i - 1]
		cum2[i] = cum2[i - 1] + diff2[i - 1]
		cum3[i] = cum3[i - 1] + diff3[i - 1]
	sol = cum1[k] - cum1[0]
	for i in range(1, n - k + 2):
		sol = min(sol, cum1[i + k - 1] - cum1[i - 1])
		sol = min(sol, cum2[i + k - 1] - cum2[i - 1])
		sol = min(sol, cum3[i + k - 1] - cum3[i - 1])
	print(sol)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(str(input())[:-1])
	s = 'RGB' * (n // 3 + 2)
	res = float('inf')
	for i in range(3):
		st = s[i:n + i]
		s0 = [0 if arr[j] == st[j] else 1 for j in range(n)]
		temp = sum(s0[:k])
		res = min(res, temp)
		for j in range(k, n):
			temp += s0[j] - s0[j - k]
			res = min(res, temp)
	print(res)


import sys
q = int(sys.stdin.readline())
for Q in range(q):
	(n, k) = map(int, sys.stdin.readline().split())
	s = sys.stdin.readline()
	dp = [0] * 3
	if n == 1 or k == 1:
		print(0)
	else:
		s1 = 0
		for i in range(k):
			if i % 3 == 0 and s[i] != 'R':
				s1 += 1
			elif i % 3 == 1 and s[i] != 'G':
				s1 += 1
			elif i % 3 == 2 and s[i] != 'B':
				s1 += 1
		dp[0] = s1
		s2 = 0
		for i in range(k):
			if i % 3 == 0 and s[i] != 'B':
				s2 += 1
			elif i % 3 == 1 and s[i] != 'R':
				s2 += 1
			elif i % 3 == 2 and s[i] != 'G':
				s2 += 1
		dp[1] = s2
		s3 = 0
		for i in range(k):
			if i % 3 == 0 and s[i] != 'G':
				s3 += 1
			elif i % 3 == 1 and s[i] != 'B':
				s3 += 1
			elif i % 3 == 2 and s[i] != 'R':
				s3 += 1
		dp[2] = s3
		for i in range(k, n):
			if i % 3 == 0 and s[i] != 'R':
				s1 += 1
			elif i % 3 == 1 and s[i] != 'G':
				s1 += 1
			elif i % 3 == 2 and s[i] != 'B':
				s1 += 1
			j = i - k
			if j % 3 == 0 and s[j] != 'R':
				s1 -= 1
			elif j % 3 == 1 and s[j] != 'G':
				s1 -= 1
			elif j % 3 == 2 and s[j] != 'B':
				s1 -= 1
			dp[0] = min(s1, dp[0])
			if i % 3 == 0 and s[i] != 'B':
				s2 += 1
			elif i % 3 == 1 and s[i] != 'R':
				s2 += 1
			elif i % 3 == 2 and s[i] != 'G':
				s2 += 1
			j = i - k
			if j % 3 == 0 and s[j] != 'B':
				s2 -= 1
			elif j % 3 == 1 and s[j] != 'R':
				s2 -= 1
			elif j % 3 == 2 and s[j] != 'G':
				s2 -= 1
			dp[1] = min(s2, dp[1])
			if i % 3 == 0 and s[i] != 'G':
				s3 += 1
			elif i % 3 == 1 and s[i] != 'B':
				s3 += 1
			elif i % 3 == 2 and s[i] != 'R':
				s3 += 1
			j = i - k
			if j % 3 == 0 and s[j] != 'G':
				s3 -= 1
			elif j % 3 == 1 and s[j] != 'B':
				s3 -= 1
			elif j % 3 == 2 and s[j] != 'R':
				s3 -= 1
			dp[2] = min(s3, dp[2])
		print(min(dp))


import sys
for _ in range(int(input())):
	(n, k) = map(int, sys.stdin.readline().split())
	st = sys.stdin.readline()
	dp = [[1, 1, 1] for i in range(n + 1)]
	dp[0][0] = dp[0][1] = dp[0][2] = 0
	for i in range(n):
		if st[i] == 'R':
			dp[i + 1][0] = 0
		elif st[i] == 'G':
			dp[i + 1][1] = 0
		else:
			dp[i + 1][2] = 0
	for i in range(1, n):
		for j in range(3):
			if dp[i + 1][(j + 1) % 3] == 1:
				dp[i + 1][(j + 1) % 3] = dp[i][j] + 1
			else:
				dp[i + 1][(j + 1) % 3] = dp[i][j]
	mini = 99999999999
	j = k
	i = 0
	store = 0
	stores = 1
	while j <= n:
		for l in range(3):
			if dp[j][(l + k) % 3] - dp[i][l] < mini:
				mini = dp[j][(l + k) % 3] - dp[i][l]
				store = j
				stores = i
		j += 1
		i += 1
	print(mini)


import sys
import math
q = int(sys.stdin.readline())
for _ in range(q):
	(n, k) = map(int, sys.stdin.readline().split())
	sub = sys.stdin.readline().strip()
	ori = ['RGB', 'GBR', 'BRG']
	minVal = sys.maxsize
	for i in range(3):
		cnt = 0
		for j in range(k):
			if sub[j] != ori[i][j % 3]:
				cnt += 1
		st = 1
		end = k
		minVal = min(minVal, cnt)
		if n == k:
			pass
		else:
			for j in range(n):
				if sub[st - 1] != ori[i][(st - 1) % 3]:
					cnt -= 1
				if sub[end] != ori[i][end % 3]:
					cnt += 1
				minVal = min(minVal, cnt)
				if end == len(sub) - 1:
					break
				st += 1
				end += 1
	print(minVal)


def main():
	q = int(input())
	ans = []
	for i in range(q):
		(n, k) = map(int, input().split())
		s = input()
		min_ans = 10 ** 9
		pr1 = [0]
		pr2 = [0]
		pr3 = [0]
		for i in range(n):
			count1 = 0
			count2 = 0
			count3 = 0
			if i % 3 == 0:
				if s[i] != 'R':
					count1 += 1
				if s[i] != 'G':
					count2 += 1
				if s[i] != 'B':
					count3 += 1
			if i % 3 == 1:
				if s[i] != 'G':
					count1 += 1
				if s[i] != 'B':
					count2 += 1
				if s[i] != 'R':
					count3 += 1
			if i % 3 == 2:
				if s[i] != 'B':
					count1 += 1
				if s[i] != 'R':
					count2 += 1
				if s[i] != 'G':
					count3 += 1
			pr1.append(pr1[-1] + count1)
			pr2.append(pr2[-1] + count2)
			pr3.append(pr3[-1] + count3)
			j = i + 1
			if j >= k:
				count1 = pr1[j] - pr1[j - k]
				count2 = pr2[j] - pr2[j - k]
				count3 = pr3[j] - pr3[j - k]
				min_ans = min(min_ans, count1, count2, count3)
		ans.append(min_ans)
	print(*ans, sep='\n')
main()


import sys
input = sys.stdin.readline

def solve(s, temp, n, k):
	l = list()
	l.append(0)
	for i in range(n):
		if temp[i] != s[i]:
			l.append(l[i] + 1)
		else:
			l.append(l[i])
	mini = 1000000
	for i in range(0, n - k + 1):
		if l[i + k] - l[i] < mini:
			mini = l[i + k] - l[i]
	return mini
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	if n == 1:
		print(0)
		continue
	temp = list()
	for i in range(n):
		if i % 3 == 0:
			temp.append('R')
		elif i % 3 == 1:
			temp.append('G')
		else:
			temp.append('B')
	ans = solve(s, temp, n, k)
	for i in range(n):
		if i % 3 == 0:
			temp[i] = 'G'
		elif i % 3 == 1:
			temp[i] = 'B'
		else:
			temp[i] = 'R'
	ans = min(ans, solve(s, temp, n, k))
	for i in range(n):
		if i % 3 == 0:
			temp[i] = 'B'
		elif i % 3 == 1:
			temp[i] = 'R'
		else:
			temp[i] = 'G'
	ans = min(ans, solve(s, temp, n, k))
	print(ans)


q = int(input())
out = ''
for _ in range(q):
	(n, k) = list(map(int, input().split()))
	s = input()
	rgb = 0
	gbr = 0
	brg = 0
	RGB = 'RGB'
	for i in range(k):
		if i % 3 == 0:
			rgb += int(s[i] != 'R')
			gbr += int(s[i] != 'G')
			brg += int(s[i] != 'B')
		elif i % 3 == 1:
			rgb += int(s[i] != 'G')
			gbr += int(s[i] != 'B')
			brg += int(s[i] != 'R')
		else:
			rgb += int(s[i] != 'B')
			gbr += int(s[i] != 'R')
			brg += int(s[i] != 'G')
	minimum = min(rgb, brg, gbr)
	for i in range(k, n):
		if (i - k) % 3 == 0:
			rgb -= int(s[i - k] != 'R')
			gbr -= int(s[i - k] != 'G')
			brg -= int(s[i - k] != 'B')
		elif (i - k) % 3 == 1:
			rgb -= int(s[i - k] != 'G')
			gbr -= int(s[i - k] != 'B')
			brg -= int(s[i - k] != 'R')
		else:
			rgb -= int(s[i - k] != 'B')
			gbr -= int(s[i - k] != 'R')
			brg -= int(s[i - k] != 'G')
		if i % 3 == 0:
			rgb += int(s[i] != 'R')
			gbr += int(s[i] != 'G')
			brg += int(s[i] != 'B')
		elif i % 3 == 1:
			rgb += int(s[i] != 'G')
			gbr += int(s[i] != 'B')
			brg += int(s[i] != 'R')
		else:
			rgb += int(s[i] != 'B')
			gbr += int(s[i] != 'R')
			brg += int(s[i] != 'G')
		minimum = min(minimum, rgb, brg, gbr)
		if minimum == 0:
			break
	out += str(minimum) + '\n'
print(out)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import sys
import copy

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

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = get_ints()
	s = input()
	R = [0] * n
	G = [0] * n
	B = [0] * n
	st = 'RGBRGB'
	d = {'R': 3, 'G': 4, 'B': 5}
	if s[0] == 'R':
		R[0] = 0
		G[0] = 1
		B[0] = 1
	if s[0] == 'B':
		B[0] = 0
		G[0] = 1
		R[0] = 1
	if s[0] == 'G':
		G[0] = 0
		R[0] = 1
		B[0] = 1
	for i in range(1, n):
		if s[i] == 'R':
			R[i] = B[i - 1]
			G[i] = 1 + R[i - 1]
			B[i] = 1 + G[i - 1]
		if s[i] == 'B':
			B[i] = G[i - 1]
			G[i] = 1 + R[i - 1]
			R[i] = 1 + B[i - 1]
		if s[i] == 'G':
			G[i] = R[i - 1]
			B[i] = 1 + G[i - 1]
			R[i] = 1 + B[i - 1]
	mini = inf
	for i in range(len(s)):
		if i >= k - 1:
			if i == k - 1:
				mini = min(mini, G[i])
				mini = min(mini, R[i])
				mini = min(mini, B[i])
			else:
				ans = k % 3
				ele_G = st[d['G'] - ans]
				ele_R = st[d['R'] - ans]
				ele_B = st[d['B'] - ans]
				if ele_G == 'G':
					mini = min(mini, G[i] - G[i - k])
				if ele_G == 'R':
					mini = min(mini, G[i] - R[i - k])
				if ele_G == 'B':
					mini = min(mini, G[i] - B[i - k])
				if ele_R == 'G':
					mini = min(mini, R[i] - G[i - k])
				if ele_R == 'R':
					mini = min(mini, R[i] - R[i - k])
				if ele_R == 'B':
					mini = min(mini, R[i] - B[i - k])
				if ele_B == 'G':
					mini = min(mini, B[i] - G[i - k])
				if ele_B == 'R':
					mini = min(mini, B[i] - R[i - k])
				if ele_B == 'B':
					mini = min(mini, B[i] - B[i - k])
	print(mini)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bfs(g, st, lcatable, level):
	visited = [0] * len(g)
	visited[st] = 1
	queue = []
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.pop()
		new.append(s)
		for i in g[s]:
			if visited[i] == 0:
				level[i] = level[s] + 1
				lcatable[i][0] = s
				visited[i] = 1
				queue.append(i)
	return new

def lcatable(g, n, level):
	mx = 0
	while 2 ** mx <= n:
		mx += 1
	lcatable = [[-1] * mx for i in range(n + 1)]
	bfs(g, 1, lcatable, level)
	for j in range(1, mx):
		for i in range(1, n + 1):
			if lcatable[i][j - 1] != -1:
				lcatable[i][j] = lcatable[lcatable[i][j - 1]][j - 1]
	return lcatable

def dist(x0, y0, x1, y1):
	return abs(x0 - x1) + abs(y0 - y1)

def solve():
	(n, k) = sep()
	s = list(inp())
	for i in range(n):
		if s[i] == 'B':
			s[i] = 2
		if s[i] == 'G':
			s[i] = 1
		if s[i] == 'R':
			s[i] = 0
	ans = 10 ** 10
	pre1 = [0] * (n + 1)
	pre2 = [0] * (n + 1)
	pre3 = [0] * (n + 1)
	ind = 0
	for j in range(0, n):
		if s[ind] != j % 3:
			pre1[ind] = pre1[ind - 1] + 1
		else:
			pre1[ind] = pre1[ind - 1]
		ind += 1
	ind = 0
	for j in range(1, 1 + n):
		if s[ind] != j % 3:
			pre2[ind] = pre2[ind - 1] + 1
		else:
			pre2[ind] = pre2[ind - 1]
		ind += 1
	ind = 0
	for j in range(2, 2 + n):
		if s[ind] != j % 3:
			pre3[ind] = pre3[ind - 1] + 1
		else:
			pre3[ind] = pre3[ind - 1]
		ind += 1
	for i in range(0, n - (k - 1)):
		cnt1 = pre1[i + k - 1] - pre1[i - 1]
		cnt2 = pre2[i + k - 1] - pre2[i - 1]
		cnt3 = pre3[i + k - 1] - pre3[i - 1]
		ans = min(ans, cnt1, cnt2, cnt3)
	print(ans)
testcase(int(inp()))


import atexit, io, sys
input_lines = sys.stdin.read().splitlines()
input = iter(input_lines).__next__
out_buffer = io.StringIO()
sys.stdout = out_buffer

@atexit.register
def write():
	sys.__stdout__.write(out_buffer.getvalue())

def line():
	inp = input().split()
	if len(inp) == 1:
		return int(inp[0])
	return map(int, inp)
from itertools import repeat, cycle
q = line()
for _ in repeat(None, q):
	(n, k) = line()
	s = input()
	w = []
	for i in range(3):
		rgb = cycle('RGB')
		for _ in repeat(None, i):
			next(rgb)
		e = [c != next(rgb) for c in s]
		r = sum(e[:k])
		m = r
		for j in range(n - k):
			r += e[j + k] - e[j]
			m = min(m, r)
		w.append(m)
	print(min(w))


from sys import stdin
input = stdin.readline
t = int(input())

def foo(seq, index):
	if index == None:
		return seq[0]
	index = index % 3
	return seq[index]
for j in range(t):
	(n, k) = list(map(int, input().split(' ')))
	chars = list(input())
	chars.insert(0, None)
	diff = [[] for i in range(n + 1)]
	diff[0] = [0, 0, 0]
	for i in range(1, n + 1):
		diff[i].append(foo('RGB', i - 1) != chars[i])
		diff[i].append(foo('GBR', i - 1) != chars[i])
		diff[i].append(foo('BRG', i - 1) != chars[i])
	for i in range(2, n + 1):
		diff[i][0] += diff[i - 1][0]
		diff[i][1] += diff[i - 1][1]
		diff[i][2] += diff[i - 1][2]
	res = float('inf')
	for i in range(k, n + 1):
		res = min(res, diff[i][0] - diff[i - k][0])
		res = min(res, diff[i][1] - diff[i - k][1])
		res = min(res, diff[i][2] - diff[i - k][2])
	print(res)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

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

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
ST = 'RGB' * 10 ** 5
for _ in range(inp()):
	(n, k) = inpl()
	s = inpsl(n)
	res = INF
	for stj in range(3):
		a = [0] * n
		for i in range(n):
			if s[i] != ST[stj + i]:
				a[i] = 1
		ans = sum((a[i] for i in range(k - 1)))
		for i in range(k - 1, n):
			ans += a[i]
			res = min(res, ans)
			ans -= a[i - k + 1]
	print(res)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	(n, k) = value()
	s = input()
	s1 = 'RGB' * k
	need = [s1[:k], s1[1:k + 1], s1[2:k + 2]]
	dp = [[0 for i in range(n)] for i in range(3)]
	for i in range(k):
		if s[i] != need[0][i]:
			dp[0][k - 1] += 1
		if s[i] != need[1][i]:
			dp[1][k - 1] += 1
		if s[i] != need[2][i]:
			dp[2][k - 1] += 1
	for i in range(k, n):
		prev = s[i - k]
		now = s[i]
		dp[0][i] = int(now != need[0][-1]) + (dp[2][i - 1] - int(prev != need[2][0]))
		dp[1][i] = int(now != need[1][-1]) + (dp[0][i - 1] - int(prev != need[0][0]))
		dp[2][i] = int(now != need[2][-1]) + (dp[1][i - 1] - int(prev != need[1][0]))
	ans = k
	for i in range(k - 1, n):
		ans = min(ans, dp[0][i], dp[1][i], dp[2][i])
	print(ans)


from sys import stdin
from collections import deque
c = int(stdin.readline().strip())
for cas in range(c):
	(n, m) = list(map(int, stdin.readline().strip().split()))
	s = deque(stdin.readline().strip())
	arr = ['R', 'G', 'B']
	ans = n + 3
	for k in range(1):
		for i in range(3):
			x = i
			dp = [0 for i in range(n + 1)]
			for j in range(n):
				if s[j] != arr[x]:
					dp[j + 1] += 1
				dp[j + 1] += dp[j]
				if j + 1 >= m:
					ans = min(ans, dp[j + 1] - dp[j + 1 - m])
				x += 1
				x = x % 3
	print(ans)
1


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	ans = 10 ** 9
	a = ['R', 'G', 'B']
	for l in range(3):
		x = l
		dp = [0] * (n + 1)
		cnt = 10 ** 9
		for i in range(n):
			if s[i] != a[x]:
				dp[i + 1] = dp[i] + 1
			else:
				dp[i + 1] = dp[i]
			x = (x + 1) % 3
		for i in range(1, n - k + 2):
			cnt = min(cnt, dp[i + k - 1] - dp[i - 1])
		ans = min(cnt, ans)
	print(ans)


import sys
A = 'RGB'
B = 'GBR'
C = 'BRG'
for nt in range(int(sys.stdin.readline())):
	(n, k) = map(int, sys.stdin.readline().split())
	s = sys.stdin.readline()
	a = b = c = 0
	for i in range(k):
		if s[i] != A[i % 3]:
			a += 1
		if s[i] != B[i % 3]:
			b += 1
		if s[i] != C[i % 3]:
			c += 1
	ans = min(a, b, c)
	for i in range(k, n):
		if s[i - k] != A[(i - k) % 3]:
			a -= 1
		if s[i - k] != B[(i - k) % 3]:
			b -= 1
		if s[i - k] != C[(i - k) % 3]:
			c -= 1
		if s[i] != A[i % 3]:
			a += 1
		if s[i] != B[i % 3]:
			b += 1
		if s[i] != C[i % 3]:
			c += 1
		ans = min(ans, a, b, c)
	print(ans)


def two(x):
	for i in range(len(x) - 1):
		if x[i] == 'R' and x[i + 1] == 'G':
			return 0
		elif x[i] == 'G' and x[i + 1] == 'B':
			return 0
		elif x[i] == 'B' and x[i + 1] == 'R':
			return 0
	return 1
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	x = input()
	if k == 1:
		print(0)
		continue
	elif k == 2:
		print(two(x))
		continue
	d = [['R', 'G', 'B'], ['G', 'B', 'R'], ['B', 'R', 'G']]
	ans = 10 ** 10
	for j in range(3):
		count = 0
		for i in range(k):
			if x[i] != d[j][i % 3]:
				count += 1
		ans = min(ans, count)
		for i in range(k, n):
			if x[i] != d[j][i % 3]:
				count += 1
			if x[i - k] != d[j][(i - k) % 3]:
				count -= 1
			ans = min(ans, count)
	print(ans)


from sys import stdin, stdout
riga = stdin.readline()
query = int(riga)
for i in range(query):
	riga = stdin.readline()
	test = riga.split()
	n = int(test[0])
	k = int(test[1])
	check = [['R', 'G', 'B'], ['G', 'B', 'R'], ['B', 'R', 'G']]
	dp = [[], [], []]
	sol = [0, 0, 0]
	for i in range(n):
		for j in range(3):
			dp[j].append(0)
	stringa = stdin.readline()
	risultato = -1
	for i in range(n):
		if i >= k:
			for j in range(3):
				sol[j] = sol[j] - dp[j][i - k]
		for j in range(3):
			if check[j][i % 3] != stringa[i]:
				dp[j][i] = 1
			sol[j] = sol[j] + dp[j][i]
			if i >= k - 1:
				if risultato == -1:
					risultato = sol[j]
				else:
					risultato = min(risultato, sol[j])
	stdout.write(str(risultato) + '\n')


from math import inf
import sys

def solve(n, k, s):
	D = [[0] * n for _ in range(3)]
	A = 'RGB'
	for d in range(3):
		idx = d
		for i in range(n):
			if A[idx] != s[i]:
				D[d][i] = 1
			idx = (idx + 1) % 3
	ans = inf
	for d in range(3):
		(i, j) = (0, k)
		cur = sum(D[d][:j])
		ans = min(ans, cur)
		while j < n:
			cur += D[d][j] - D[d][i]
			j += 1
			i += 1
			ans = min(ans, cur)
	return ans
for nt in range(int(sys.stdin.readline())):
	(n, k) = map(int, sys.stdin.readline().split())
	s = sys.stdin.readline()
	print(solve(n, k, s))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = input()
	c1 = c2 = c3 = 0
	s1 = 'RGB'
	s2 = 'GBR'
	s3 = 'BRG'
	ans = n
	for i in range(k):
		if s[i] != s1[i % 3]:
			c1 += 1
		if s[i] != s2[i % 3]:
			c2 += 1
		if s[i] != s3[i % 3]:
			c3 += 1
	ans = min(ans, min(c1, c2, c3))
	for i in range(k, n):
		if s[i] != s1[i % 3]:
			c1 += 1
		if s[i - k] != s1[(i - k) % 3]:
			c1 -= 1
		if s[i] != s2[i % 3]:
			c2 += 1
		if s[i - k] != s2[(i - k) % 3]:
			c2 -= 1
		if s[i] != s3[i % 3]:
			c3 += 1
		if s[i - k] != s3[(i - k) % 3]:
			c3 -= 1
		ans = min(ans, min(c1, c2, c3))
	print(ans)


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s1 = 'RGB'
	dp = [[0, 0, 0] for i in range(n)]
	ans = 10 ** 18
	for i in range(3):
		for j in range(k):
			if s[j] != s1[(i + j) % 3]:
				dp[0][i] += 1
		ans = min(ans, dp[0][i])
		for j in range(1, n - k + 1):
			if s[j - 1] != s1[(i + j - 1) % 3]:
				dp[j][i] += dp[j - 1][i] - 1
			else:
				dp[j][i] += dp[j - 1][i]
			if s[j + k - 1] != s1[(i + j + k - 1) % 3]:
				dp[j][i] += 1
			ans = min(ans, dp[j][i])
	print(ans)


import sys
input = sys.stdin.readline
q = int(input())
aux = 'RGB'

def fun(k, s, ini):
	tam = 0
	ans = int(1e+20)
	change = 0
	i = 0
	j = 0
	while len(s) > i:
		while len(s) > i and k > tam:
			change += 1 if aux[(ini + i) % 3] != s[i] else 0
			tam += 1
			i += 1
		if tam == k:
			ans = min(ans, change)
		change -= 1 if s[j] != aux[(ini + j) % 3] else 0
		j += 1
		tam -= 1
	return ans
for _ in range(q):
	(n, k) = map(int, input().split(' '))
	s = input()
	print(min(fun(k, s, 0), min(fun(k, s, 1), fun(k, s, 2))))


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left, bisect_right
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mi = k
	s = input()
	l = deque()
	d = {'R': 0, 'G': 1, 'B': 2}
	for i in range(3):
		l.append([0, 0, 0])
	for i in range(k - 1):
		l[i % 3][d[s[i]]] += 1
	a = 0
	for i in range(k - 1, n):
		l[i % 3][d[s[i]]] += 1
		t = l[0][1] + l[0][2] + l[1][0] + l[1][2] + l[2][0] + l[2][1]
		t1 = l[0][1] + l[0][0] + l[1][1] + l[1][2] + l[2][0] + l[2][2]
		t2 = l[0][0] + l[0][2] + l[1][0] + l[1][1] + l[2][2] + l[2][1]
		mi = min(mi, t, t1, t2)
		l[a % 3][d[s[a]]] -= 1
		a += 1
	print(mi)


import sys, os, io

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, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = ri()
	for _ in range(tc):
		(n, k) = ria()
		s = list(rs())
		a = 'RGB' * n
		b = 'BRG' * n
		c = 'GBR' * n
		a = a[:n]
		b = b[:n]
		c = c[:n]
		z = [a, b, c]
		da = [0] * n
		db = [0] * n
		dc = [0] * n
		for i in range(n):
			if s[i] == a[i]:
				da[i] = 1
			elif s[i] == b[i]:
				db[i] = 1
			else:
				dc[i] = 1
		pda = [0]
		pdb = [0]
		pdc = [0]
		for i in range(n):
			pda.append(pda[-1] + da[i])
			pdb.append(pdb[-1] + db[i])
			pdc.append(pdc[-1] + dc[i])
		maxs = 0
		for i in range(k, n + 1):
			sa = pda[i] - pda[i - k]
			sb = pdb[i] - pdb[i - k]
			sc = pdc[i] - pdc[i - k]
			maxs = max(maxs, sa, sb, sc)
		print(k - maxs)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


from sys import stdin
input = stdin.readline
q = int(input())
for ppppp in range(q):
	[n, k] = [int(item) for item in input().split(' ')]
	x = input()
	inf_seq = 'RGB'
	ptr = 0
	weights = []
	cost = [0, 0, 0]
	for i in range(k):
		dd = [0, 0, 0]
		for d in range(3):
			if x[i] != inf_seq[(i + d) % 3]:
				dd[d] = 1
				cost[d] += 1
		weights.append(dd)
	min_changes = min(cost)
	for i in range(k, n):
		dd = [0, 0, 0]
		for d in range(3):
			cost[d] -= weights[i - k][d]
			if x[i] != inf_seq[(i + d) % 3]:
				dd[d] = 1
				cost[d] += 1
		weights.append(dd)
		min_changes = min(min_changes, min(cost))
	print(min_changes)


import math
import sys
input = sys.stdin.readline
q = int(input())
for j in range(q):
	(n, k) = map(int, input().split())
	s = input()
	cycle = ['R', 'G', 'B']
	mina = math.inf
	for i in range(3):
		ans = [0] * n
		c = 0
		for j in range(n):
			if s[j] != cycle[(i + j) % 3]:
				ans[j] += 1
			c += ans[j]
			if j >= k:
				c -= ans[j - k]
			if j >= k - 1:
				mina = min(mina, c)
	sys.stdout.write(str(mina) + '\n')


import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()
for _ in range(t):
	(n, k) = gil()
	s = g()
	w = [0, 0, 0]
	p = ['RGB', 'GBR', 'BRG']
	for i in range(k):
		for pi in range(3):
			w[pi] += 1 if p[pi][i % 3] != s[i] else 0
	fi = w[:]
	for i in range(k, n):
		for pi in range(3):
			w[pi] -= 1 if p[pi][(i - k) % 3] != s[i - k] else 0
			w[pi] += 1 if p[pi][i % 3] != s[i] else 0
			fi[pi] = min(fi[pi], w[pi])
	print(min(fi))


import sys
input = sys.stdin.readline
a = int(input())
for i in range(a):
	(n, k) = map(int, input().split())
	dp = [[0 for i in range(n - k + 1)] for i in range(3)]
	s = input()
	c1 = 0
	c2 = 0
	c3 = 0
	for i in range(k):
		if i % 3 == 0:
			if s[i] == 'R':
				c2 += 1
				c3 += 1
			elif s[i] == 'G':
				c1 += 1
				c3 += 1
			else:
				c1 += 1
				c2 += 1
		if i % 3 == 1:
			if s[i] == 'R':
				c1 += 1
				c2 += 1
			if s[i] == 'G':
				c2 += 1
				c3 += 1
			if s[i] == 'B':
				c1 += 1
				c3 += 1
		if i % 3 == 2:
			if s[i] == 'R':
				c1 += 1
				c3 += 1
			elif s[i] == 'G':
				c1 += 1
				c2 += 1
			else:
				c2 += 1
				c3 += 1
	dp[0][0] = c1
	dp[1][0] = c2
	dp[2][0] = c3
	mini = min(c1, c2, c3)
	for i in range(1, n - k + 1):
		dp[0][i] = dp[2][i - 1] - int(s[i - 1] != 'B')
		dp[1][i] = dp[0][i - 1] - int(s[i - 1] != 'R')
		dp[2][i] = dp[1][i - 1] - int(s[i - 1] != 'G')
		t = i + k - 1
		if s[t] == 'R':
			if k % 3 == 0:
				dp[0][i] += 1
				dp[2][i] += 1
			if k % 3 == 1:
				dp[2][i] += 1
				dp[1][i] += 1
			if k % 3 == 2:
				dp[0][i] += 1
				dp[1][i] += 1
		if s[t] == 'G':
			if k % 3 == 0:
				dp[0][i] += 1
				dp[1][i] += 1
			if k % 3 == 1:
				dp[0][i] += 1
				dp[2][i] += 1
			if k % 3 == 2:
				dp[1][i] += 1
				dp[2][i] += 1
		if s[t] == 'B':
			if k % 3 == 0:
				dp[1][i] += 1
				dp[2][i] += 1
			if k % 3 == 1:
				dp[0][i] += 1
				dp[1][i] += 1
			if k % 3 == 2:
				dp[0][i] += 1
				dp[2][i] += 1
		mini = min(mini, dp[0][i], dp[1][i], dp[2][i])
	print(mini)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = input()
	s = 'RGB'
	minim = k
	for j in range(3):
		d = [0] * (n + 1)
		for i in range(n):
			d[i + 1] = d[i] if s[(i + j) % 3] == l[i] else d[i] + 1
			if i >= k - 1:
				minim = min(minim, d[i + 1] - d[i + 1 - k])
	print(minim)


from sys import stdin, stdout
inp = stdin.readline
for _ in range(int(inp())):
	(n, k) = map(int, inp().split())
	(a, b, c, ans) = ([0], [0], [0], 200000.0 + 5)
	s = inp()
	for i in range(n):
		a.append(a[-1] + (s[i] != 'RGB'[i % 3]))
		b.append(b[-1] + (s[i] != 'GBR'[i % 3]))
		c.append(c[-1] + (s[i] != 'BRG'[i % 3]))
	for i in range(n - k + 1):
		ans = min(ans, a[i + k] - a[i], b[i + k] - b[i], c[i + k] - c[i])
	stdout.write(str(ans) + '\n')


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	l = stdin.readline()
	m = float('inf')
	for q in range(3):
		if q == 0:
			s = 'RGB'
		elif q == 1:
			s = 'GBR'
		else:
			s = 'BRG'
		(i, count, c) = (0, 0, 0)
		while i < k:
			if l[i] != s[c]:
				count += 1
			i += 1
			c += 1
			if c == 3:
				c = 0
		m = min(m, count)
		last = s[0]
		while i < n:
			if l[i - k] != last:
				count -= 1
			if l[i] != s[c]:
				count += 1
			i += 1
			c += 1
			if c == 3:
				c = 0
			m = min(m, count)
			if last == s[0]:
				last = s[1]
			elif last == s[1]:
				last = s[2]
			else:
				last = s[0]
	print(m)


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	for color in ['RGB', 'GBR', 'BRG']:
		cnt = 0
		for i in range(k):
			if s[i] == color[i % 3]:
				cnt += 1
		maxi = cnt
		for i in range(n - k):
			if s[i + k] == color[(i + k) % 3]:
				cnt += 1
			if s[i] == color[i % 3]:
				cnt -= 1
			if cnt > maxi:
				maxi = cnt
		ans = max(ans, maxi)
	print(k - ans)


import os
import sys
from io import BytesIO, IOBase
from math import inf

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = list(input().rstrip())
		a = ['RGB', 'GBR', 'BRG']
		dp = [[0 for _ in range(n + 1)] for _ in range(3)]
		for j in range(3):
			for i in range(n):
				dp[j][i + 1] = (s[i] != a[j][i % 3]) + dp[j][i]
		mi = inf
		for i in range(n - k + 1):
			for j in range(3):
				mi = min(mi, dp[j][i + k] - dp[j][i])
		print(mi)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from itertools import accumulate
import sys
readline = sys.stdin.readline
q = int(readline())
for query in range(q):
	(n, k) = map(int, readline().split())
	s = readline()[:-1]
	RGB = 'RGB'
	sum = [[0] * n] * 3
	res = n
	for i in range(3):
		for j in range(n):
			sum[i][j] = int(s[j] != RGB[(i + j) % 3])
		sum[i] = list(accumulate(sum[i]))
		tmp = sum[i][k - 1]
		for j in range(k, n):
			tmp = min(tmp, sum[i][j] - sum[i][j - k])
		res = min(res, tmp)
	print(res)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = [i for i in input().strip()]
	if k == 1:
		print(0)
	else:
		seq = ['R', 'G', 'B']
		dp = [[0] * n for i in range(3)]
		dp[0][0] = int(s[0] != 'R')
		dp[1][0] = int(s[0] != 'G')
		dp[2][0] = int(s[0] != 'B')
		ct = 10 ** 6
		for i in range(1, n):
			dp[0][i] = dp[2][i - 1] + (s[i] != 'R')
			dp[1][i] = dp[0][i - 1] + (s[i] != 'G')
			dp[2][i] = dp[1][i - 1] + (s[i] != 'B')
			if i >= k - 1:
				ct = min(ct, (s[i + 1 - k] != seq[(1 - k) % 3]) + dp[0][i] - dp[(1 - k) % 3][1 + i - k])
				ct = min(ct, (s[i + 1 - k] != seq[(2 - k) % 3]) + dp[1][i] - dp[(2 - k) % 3][1 + i - k])
				ct = min(ct, (s[i + 1 - k] != seq[(3 - k) % 3]) + dp[2][i] - dp[(3 - k) % 3][1 + i - k])
		print(ct)


import sys

def process(S, k, n):
	if k == 1:
		return 0
	answer = float('inf')
	current = [0, 0, 0]
	indexes = {'R': 0, 'G': 1, 'B': 2}
	for i in range(k):
		c = chr(S[i])
		index = (indexes[c] - i) % 3
		for j in range(3):
			current[j] += 1
		current[index] -= 1
	answer = min(answer, min(current))
	for i in range(k, n):
		c1 = chr(S[i - k])
		index1 = (indexes[c1] - i + k) % 3
		for j in range(3):
			current[j] -= 1
		current[index1] += 1
		c = chr(S[i])
		index = (indexes[c] - i) % 3
		for j in range(3):
			current[j] += 1
		current[index] -= 1
		answer = min(answer, min(current))
	return answer
input = sys.stdin.buffer.readline
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	S = input()
	if k == 1:
		print(0)
	else:
		print(process(S, k, n))