Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You work as an engineer. You were given an empty board with $K$ consecutive cells; at any moment, each cell can display one character.

You want the board to display a string $S$ with length $N > K$. Since the board isn't large enough, you want to display the string in $N-K+1$ steps. In the $i$-th step ($1 ≤ i ≤ N-K+1$), you'll make the board display the characters $S_{i}, S_{i+1}, \dots, S_{i+K-1}$.

The power required to switch the board from step $i$ to step $i+1$ (for $1 ≤ i ≤ N-K$) is equal to the number of characters displayed on the board that have to change between these steps. You should find the total power required for the whole process of displaying a string, i.e. the sum of powers required for switching between all consecutive pairs of steps.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains a single string $S$ with length $N$.

------  Output ------
For each test case, print a single line containing one integer — the total power required for text switching.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ K < N$
each character of $S$ is a lowercase English letter
the sum of $N$ for all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (20 points):
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 50$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
3
6 3
aabbcc
5 2
abccc
4 3
aabb
----- Sample Output 1 ------ 
4
3
1
----- explanation 1 ------ 
Example case 1:
- In step $1$, the board is displaying "aab".
- In step $2$, the board is displaying "abb".
- In step $3$, the board is displaying "bbc".
- In step $4$, the board is displaying "bcc".

The power required for switching from the $1$-st to the $2$-nd step is $1$, because cell $1$ changes from 'a' to 'a' (requiring power $0$), cell $2$ changes from 'a' to 'b' (requiring power $1$) and cell $3$ changes from 'b' to 'b' (requiring power $0$); $0 + 1 + 0 = 1$.

The power required for switching between the $2$-nd and $3$-rd step is $2$ and the power required for switching between the $3$-rd and $4$-th step is $1$.

Therefore, the answer is $1 + 2 + 1 = 4$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures


Solutions:
case = int(input())
for _ in range(case):
	(n, k) = map(int, input().split(' '))
	s = input()
	arr = []
	if n & 1 == 1:
		value = n // 2
		for i in range(value):
			arr.append(i + 1)
		for i in range(value, n):
			arr.append(value)
			value -= 1
	else:
		value = n // 2
		for i in range(value):
			arr.append(i + 1)
		for i in range(value, n):
			value -= 1
			arr.append(value)
	ans = 0
	if k <= n // 2:
		ans = k
	else:
		ans = n - k
	res = 0
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			if arr[i] <= ans:
				res += arr[i]
			else:
				res += ans
	print(res)


from collections import deque

def ans(k, s):
	if k == 1:
		cnt = 0
		for i in range(0, len(s) - 1):
			if s[i + 1] != s[i]:
				cnt += 1
		return cnt
	else:
		s = list(s)
		i = 0
		j = k - 1
		d = deque(s[i:j + 1])
		ncons = 0
		for i in range(0, len(d) - 1):
			if d[i + 1] != d[i]:
				ncons += 1
		cnt = 0
		while j < len(s) - 1:
			cnt += ncons
			t1 = d.popleft()
			d.append(s[j + 1])
			if d[-2] != d[-1]:
				cnt += 1
				ncons += 1
			if t1 != d[0]:
				ncons -= 1
			j += 1
		return cnt
test_cases = int(input())
while test_cases != 0:
	d = list(map(int, input().split()))
	d2 = input()
	print(ans(d[-1], d2))
	test_cases -= 1


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	diff = [0] * n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			diff[i] = 1
	sum = 0
	for i in range(k):
		if diff[i] == 1:
			sum += 1
	ans = 0
	for i in range(1, n - k + 1):
		sum += diff[i + k - 1] - diff[i - 1]
		ans += sum
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = str(input())
	steps = [0 for i in range(k)]
	for j in range(n - k):
		if s[j] != s[j + 1]:
			steps[0] += 1
	for l in range(1, k):
		steps[l] = steps[l - 1]
		old = l
		new = l + n - k
		if s[old] != s[old - 1]:
			steps[l] -= 1
		if s[new] != s[new - 1]:
			steps[l] += 1
	print(sum(steps))


def FindPower(arr, n, k):
	change_arr = [1 if arr[i] != arr[i + 1] else 0 for i in range(n - 1)]
	summ = sum(change_arr[:k])
	res = 0
	res += summ
	for i in range(1, n - k):
		summ += change_arr[k + i - 1]
		summ -= change_arr[i - 1]
		res += summ
	return res
for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = input()
	print(FindPower(arr, n, k))


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	S = input()
	dp = [0] + [1 if S[i] != S[i - 1] else 0 for i in range(1, N)]
	ans = 0
	i = 1
	sum_ = sum(dp[1:K + 1])
	ans += sum_
	while i + K < len(S):
		sum_ += dp[i + K]
		sum_ -= dp[i]
		ans += sum_
		i = i + 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	cnt = [0] * n
	sm = 0
	for i in range(0, n - 1):
		if s[i] != s[i + 1]:
			cnt[i] = 1
	psum = [0] * (n + 1)
	psum[0] = 0
	for i in range(1, n + 1):
		psum[i] = psum[i - 1] + cnt[i - 1]
	for i in range(n - k):
		sm += psum[i + k] - psum[i]
	print(sm)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	sm = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			sm += min(i, k, n - k, n - i)
	print(sm)


import math

def get_power(a, b):
	if a == b:
		return 0
	return 1

def sum_power(x, N, K):
	sum = 0
	end = math.ceil(N / 2)
	max_prod = K if K <= end else N - K + 1
	for i in range(1, end + 1):
		temp = i
		if i > max_prod:
			temp = max_prod
		sum += temp * x[i - 1] + temp * x[N - i]
	if N % 2 == 1:
		sum -= temp * x[i - 1]
	return sum

def find_sum_power(S, N, K):
	consecutive_cell_power = []
	for i in range(N - 1):
		consecutive_cell_power.append(get_power(S[i], S[i + 1]))
	return sum_power(consecutive_cell_power, N - 1, K)
for i in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	print(find_sum_power(S, N, K))


def con(a, b):
	cou = 0
	for i in range(1, a[0]):
		if b[i - 1] != b[i]:
			if i > a[1] - 1 and i < a[0] - a[1]:
				cou += a[1]
			elif i - a[1] < 0:
				if a[0] - i > a[1]:
					cou += i
				else:
					cou += min(a[0] - i - 1, a[0] - a[1])
			else:
				cou += a[0] - i
	print(cou)
for _ in range(int(input())):
	con(list(map(int, input().split(' '))), input())


def lisin():
	a = list(map(int, input().split()))
	return a
for tastcas in range(int(input())):
	(n, k) = lisin()
	a = input()
	ch = [0] * k
	kk = k - 1
	nn = n - 1
	for i in range(k):
		if a[i] == a[i + 1]:
			ch[i] = 1
	need = ch.count(0)
	pow = 0
	while k < nn:
		pow += need
		if ch[0] == 0:
			need -= 1
		if a[k] == a[k + 1]:
			ch.append(1)
			ch.pop(0)
		else:
			ch.append(0)
			ch.pop(0)
			need += 1
		k += 1
	print(pow + need)


cases_num = int(input())
for _ in range(cases_num):
	(str_len, board_len) = [int(num) for num in input().split()]
	string = input()
	power_req = 0
	repeats = 0
	for i in range(1, str_len):
		if string[i] == string[i - 1]:
			repeats += 1
		if i - board_len > 0 and string[i - board_len - 1] == string[i - board_len]:
			repeats -= 1
		if i >= board_len:
			power_req += board_len - repeats
	print(power_req)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = [0] * n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			d[i] = 1
	for i in range(1, n):
		d[i] += d[i - 1]
	res = 0
	for i in range(k):
		res += d[i + (n - k)] - d[i]
	print(res)


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

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

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

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def main():
	for _ in tr():
		(n, k) = sm()
		string = line()
		saved = 0
		for i in range(n - 1):
			if string[i + 1] == string[i]:
				saved += min(n - k, i + 1, n - i - 1, k)
		print(k * (n - k) - saved)
main()


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	res = 0
	diff = [0] * N
	for i in range(1, N):
		if S[i - 1] != S[i]:
			diff[i] = 1
		else:
			diff[i] = 0
	for i in range(1, N):
		diff[i] += diff[i - 1]
	for i in range(K):
		res += diff[i + (N - K)] - diff[i]
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	ans = 0
	size = n - k + 1
	last = -1
	lastcnt = 0
	for i in range(size):
		if last == -1:
			last = s[i]
		elif last != s[i]:
			lastcnt += 1
			last = s[i]
	ans += lastcnt
	for i in range(size, n):
		if s[i - size] != s[i - size + 1]:
			lastcnt -= 1
		if last != s[i]:
			lastcnt = lastcnt + 1
		ans += lastcnt
		last = s[i]
	print(ans)


def solve(board_size: int, word_size: int, word: str) -> int:
	changes = 0
	for i in range(1, word_size):
		if word[i] != word[i - 1]:
			changes += board_size - max(board_size - i, 0) - max(i - (word_size - board_size), 0)
	return changes

def main():
	tests = int(input())
	for _ in range(tests):
		sizes = input().split()
		word_size = int(sizes[0])
		board_size = int(sizes[1])
		word = input()
		changes = solve(board_size, word_size, word)
		print(changes)
main()


tc = input()
for q in range(int(tc)):
	(n, k) = map(int, input().split())
	s = input()
	i = 1
	SUMPOWER = 0
	while i != n:
		if s[i] == s[i - 1]:
			i += 1
			continue
		elif i <= k - 1:
			SUMPOWER += min(i, n - k)
		elif i >= n - k:
			SUMPOWER += min(n - i, n - k)
		else:
			SUMPOWER += k
		i += 1
	print(SUMPOWER)


from sys import stdin, stdout
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	s = input().strip()
	arr = list()
	psum = list()
	total = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			arr.append(0)
		else:
			arr.append(1)
		total += arr[i]
		psum.append(total)
	ans = psum[k - 1]
	for i in range(k, n - 1):
		ans += psum[i] - psum[i - k]
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)

def pro(arr, k):
	n = len(arr)
	lst = [0] * (n - 1)
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			lst[i] = 1
	i = 0
	c = 0
	j = 0
	k1 = k
	while k1:
		c += lst[j]
		j += 1
		k1 -= 1
	ans = c
	j = k - 1
	while j < len(lst) - 1:
		if lst[i]:
			c -= 1
		if j + 1 < len(lst) and lst[j + 1]:
			c += 1
		ans += c
		i += 1
		j += 1
	print(ans)
n = int(input())
for i in range(n):
	(n, k) = list(map(int, input().split()))
	arr = list(input())
	pro(arr, k)


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	string = input()
	result = 0
	for i in range(n - 1):
		if string[i + 1] == string[i]:
			result += min(n - k, i + 1, n - 1 - i, k)
	print(k * (n - k) - result)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = str(input())
	temp_ans = [False] * k
	for i in range(k):
		if s[i] == s[i + 1]:
			temp_ans[i] = True
	ans_arr = []
	count = 0
	for i in temp_ans:
		if not i:
			count += 1
	a = count
	for i in range(k, n - 1):
		temp = temp_ans.pop(0)
		if not temp:
			count -= 1
		if s[i] != s[i + 1]:
			temp_ans.append(False)
			count += 1
		else:
			temp_ans.append(True)
		a += count
	print(a)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = str(input())
	a = 0
	v = [0]
	for j in range(n - 1):
		if s[j] != s[j + 1]:
			a += 1
		v.append(a)
	(x, y) = (0, k)
	ans = 0
	for i in range(k, n):
		ans += abs(v[x] - v[i])
		x += 1
	print(ans)


T = int(input())
for i in range(T):
	(N, K) = map(lambda x: int(x), str(input()).split(' '))
	S = str(input())
	hmuch = []
	value = 0
	for j in range(N - 1):
		if S[j] == S[j + 1]:
			value = value + 1
		hmuch.append(value)
	answer = 0
	for j in range(N - K):
		if j == 0:
			answer = answer + (K - hmuch[K - 1])
		else:
			answer = answer + (K - (hmuch[j + K - 1] - hmuch[j - 1]))
	print(answer)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	add = 0
	v = [0]
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			add += 1
		v.append(add)
	(i, j) = (0, k)
	ans = 0
	while j != 0:
		ans += v[-j] - v[i]
		i += 1
		j -= 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	data = input()
	pre = [0] * n
	for i in range(1, n):
		pre[i] = pre[i - 1]
		if data[i] != data[i - 1]:
			pre[i] += 1
	total = 0
	column = n - k
	for i in range(k):
		cost = pre[i + column] - pre[i]
		total += cost
	print(total)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	currcost = 0
	for i in range(1, k):
		if s[i] != s[i - 1]:
			currcost += 1
	ans = 0
	for j in range(k, n):
		if s[j] != s[j - 1]:
			currcost += 1
		if j - k != 0 and s[j - k] != s[j - k - 1]:
			currcost -= 1
		ans += currcost
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	check = []
	check.append(0)
	currcost = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			check.append(1)
			if i < k:
				currcost += 1
		else:
			check.append(0)
	ans = 0
	for j in range(k, n):
		if check[j - k] == 1:
			currcost -= 1
		if check[j] == 1:
			currcost += 1
		ans += currcost
	print(ans)


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	s = input()
	arr = []
	for i in range(n - 1):
		arr.append(int(s[i] != s[i + 1]))
	sm = sum(arr[:k])
	res = sm
	for i in range(n - k - 1):
		sm = sm - arr[i] + arr[i + k]
		res += sm
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	pre = [0] * n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			pre[i] = pre[i - 1] + 1
		else:
			pre[i] = pre[i - 1]
	count = 0
	for i in range(k, n):
		count += pre[i] - pre[i - k]
	print(count)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	result = 0
	diff = [0] * n
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			diff[i] = 1
		else:
			diff[i] = 0
	cost = 0
	for i in range(k):
		cost += diff[i]
	result += cost
	for i in range(n - k - 1):
		cost -= diff[i]
		cost += diff[i + k]
		result += cost
	print(result)


import math
from collections import Counter, defaultdict
import sys
mod = 10 ** 9 + 7
input = sys.stdin.readline
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr = lambda : input().strip()
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())
strList = lambda : list(input().strip().split())

def print(*args, end='\n', sep=' '):
	for i in args:
		sys.stdout.write(str(i))
		sys.stdout.write(sep)
	sys.stdout.write(end)

def solve():
	res = i = equals = 0
	for j in range(1, k):
		if s[j] == s[j - 1]:
			equals += 1
	for j in range(k, n):
		if j > i and s[j] == s[j - 1]:
			equals += 1
		if j - i == k:
			res += k - equals
		if j - i == k:
			if i < j and s[i] == s[i + 1]:
				equals -= 1
			i += 1
	return res
for _ in range(readInt()):
	(n, k) = intMap()
	s = list(input().strip())
	print(solve())


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	start = 0
	end = 0
	val = 0
	string = ''
	diff = [0] * n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			diff[i] = 1
		else:
			diff[i] = 0
	for i in range(1, n):
		diff[i] += diff[i - 1]
	ans = 0
	for i in range(k):
		ans += diff[i + (n - k)] - diff[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	pre_sum = [0] * (n + 1)
	for j in range(n):
		if j == 0:
			pre_sum[j + 1] += 1
		elif s[j] == s[j - 1]:
			pre_sum[j + 1] = pre_sum[j]
		else:
			pre_sum[j + 1] = pre_sum[j] + 1
	power = 0
	cnt = 0
	for j in range(1, n + 1):
		if cnt == k:
			power += pre_sum[j] - pre_sum[j - k]
			cnt -= 1
		cnt += 1
	print(power)


def switch_power(s, n, k):
	power = 0
	for i in range(1, n):
		if i < k and n - 1 - i < k and (s[i] != s[i - 1]):
			power += n - k
			continue
		if i < k and s[i] != s[i - 1]:
			power += i
			continue
		if n - 1 - i < k and s[i] != s[i - 1]:
			power += n - i
			continue
		if s[i] != s[i - 1]:
			power += k
		else:
			continue
	return power
T = int(input())
for t in range(T):
	(n, k) = map(int, input().strip().split())
	S = input()
	power = switch_power(S, n, k)
	print(power)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	tot = 0
	s = N - K
	s = min(s, K)
	if N >= 2 * s:
		for p in range(1, s + 1):
			if S[p] != S[p - 1]:
				tot += p
		for p in range(s + 1, N - s + 1):
			if S[p] != S[p - 1]:
				tot += s
		for p in range(N - s + 1, N):
			if S[p] != S[p - 1]:
				tot += N - p
	else:
		mx = N / 2
		for p in range(1, mx + 1):
			if S[p] != S[p - 1]:
				tot += p
		for p in range(mx + 1, N):
			if S[p] != S[p - 1]:
				tot += N - p
	print(tot)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	a = 0
	l = n - k
	h = min(l, k)
	for i in range(1, h):
		if s[i] != s[i - 1]:
			a += i
	for i in range(h, n - h + 1):
		if s[i] != s[i - 1]:
			a += h
	for i in range(n - h + 1, n):
		if s[i] != s[i - 1]:
			a += n - i
	print(a)


t = int(input())
for h in range(t):
	(n, k) = map(int, input().split())
	x = list(input())
	c = 0
	for i in range(1, k):
		if x[i] != x[i - 1]:
			c += 1
	i = 1
	j = k
	s = 0
	while j < n:
		if x[j] != x[j - 1]:
			c += 1
		s += c
		if x[i] != x[i - 1]:
			c -= 1
		i += 1
		j += 1
	print(s)


t = int(input())
for _t in range(t):
	(s, w) = map(int, input().split())
	p = input()
	a = [0 for i in range(s)]
	for i in range(1, s):
		if p[i] != p[i - 1]:
			a[i] = 1
	for i in range(1, s):
		a[i] = a[i] + a[i - 1]
	ans = 0
	for i in range(w):
		ans += a[s - w + i] - a[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = [0]
	p = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			p += 1
		l.append(p)
	i = 0
	ans = 0
	while i < len(s):
		try:
			ans += l[k + i] - l[i]
		except:
			break
		i += 1
	print(ans)


T = int(input())
ans = []
for _ in range(T):
	(N, K) = [int(i) for i in input().split()]
	S = input()
	pairs = [0]
	p = 0
	for i in range(1, N):
		if S[i - 1] == S[i]:
			p += 1
		pairs.append(p)
	sum = 0
	for i in range(N - K):
		sum += K - (pairs[i + K] - pairs[i])
	ans.append(sum)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	i = 1
	j = 1
	ans = 0
	sumi = 0
	while i < n and j < n:
		if s[j] != s[j - 1]:
			sumi += 1
		j += 1
		if j - i == k:
			ans += sumi
			if s[i] != s[i - 1]:
				sumi -= 1
			i += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	adj = [0] * n
	r = min(k, n - k)
	for i in range(1, n):
		if s[i] != s[i - 1]:
			adj[i] = 1
	ans = 0
	for i in range(n):
		ans += adj[i] * min(min(i, r), min(n - i, r))
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	dif = [0] * n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			dif[i] = dif[i - 1] + 1
		else:
			dif[i] = dif[i - 1]
	for i in range(0, k):
		ans += dif[i + (n - k)] - dif[i]
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	store = [1 for i in range(n)]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			store[i] = 0
	prev = sum(store[:k])
	ans = 0
	for i in range(1, n - k + 1):
		prev += store[i + k - 1] - store[i - 1]
		ans += prev
	print(ans)


import sys, os, io, time, copy, math
from collections import deque

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		string = input()
		arr = [0]
		for i in range(1, n):
			if string[i] != string[i - 1]:
				arr.append(1)
			else:
				arr.append(0)
		for i in range(1, n):
			arr[i] = arr[i - 1] + arr[i]
		k = n - k + 1
		result = arr[k - 1]
		for i in range(k, n):
			x = arr[i] - arr[i - k + 1]
			result += x
		print(result)
main()


def sumpower(s, k):
	diff = len(s) * [0]
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			diff[i] = 1
	for i in range(1, len(diff)):
		diff[i] += diff[i - 1]
	ans = 0
	for i in range(0, k):
		ans += diff[n - k + i] - diff[i]
	return ans
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	print(sumpower(s, k))


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		ref = [0] * n
		for i in range(1, n):
			if s[i] == s[i - 1]:
				ref[i] = True
			else:
				ref[i] = False
		points = 0
		ts = 0
		fs = 0
		for i in range(k):
			if ref[i]:
				ts += 1
			else:
				fs += 1
		l = 0
		r = k - 1
		while r != n - 1:
			if ref[l]:
				ts -= 1
			else:
				fs -= 1
			l += 1
			r += 1
			if ref[r]:
				ts += 1
			else:
				fs += 1
			points += fs
		print(points)
except:
	pass


s = ''
n = 0
k = 0

def fun():
	res = 0
	for i in range(1, n):
		if i <= n - k:
			if s[i] != s[i - 1]:
				if i >= k:
					res += k
				else:
					res += i
		elif s[i] != s[i - 1]:
			if k - 1 < i:
				res += n - i
			else:
				res += n - k
	print(res)
t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	fun()
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	dif = [0] * n
	for i in range(1, n):
		if s[i] != s[i - 1]:
			dif[i] = 1
	for i in range(1, n):
		dif[i] = dif[i] + dif[i - 1]
	c = 0
	for i in range(m):
		c += dif[n - m + i] - dif[i]
	print(c)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	res = 0
	output = 0
	s = input()
	arr = [int(s[i] != s[i + 1]) for i in range(n - 1)]
	res += sum(arr[:k])
	output += res
	for i in range(n - k - 1):
		res += arr[i + k] - arr[i]
		output += res
	print(output)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	string = input()
	final = 0
	for i in range(n - 1):
		required = min(i, k - 1)
		p = max(1, i - k + 2)
		remaining = n - k - p
		l = min(required, remaining)
		if string[i] != string[i + 1]:
			final += l + 1
	print(final)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	prev = s[0]
	c = 0
	dp = [0] * n
	for i in range(1, n):
		if prev != s[i]:
			dp[i] = dp[i - 1] + 1
		else:
			dp[i] = dp[i - 1]
		prev = s[i]
	for i in range(k):
		c += dp[i + (n - k)] - dp[i]
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	s = list(s)
	c = 0
	l = []
	if n % 2 == 0:
		for i in range(1, n // 2 + 1):
			d = min(n - k, k, i)
			l.append(d)
		for i in range(n // 2 - 1, 0, -1):
			d = min(n - k, k, i)
			l.append(d)
	else:
		for i in range(1, n // 2 + 1):
			d = min(n - k, k, i)
			l.append(d)
		for i in range(n // 2, 0, -1):
			d = min(n - k, k, i)
			l.append(d)
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			c += l[i]
	print(c)


t = int(input())
for _ in range(t):
	inp = input().split()
	n = int(inp[0])
	k = int(inp[1])
	a = input()
	c = 0
	ans = 0
	for i in range(k):
		if a[i] != a[i + 1]:
			c += 1
	for i in range(n - k):
		ans += c
		if not a[i] == a[i + 1]:
			c -= 1
		if i + k + 1 == n:
			break
		if not a[i + k] == a[i + k + 1]:
			c += 1
	print(ans)


e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = [0]
	for i in range(1, n):
		if s[i] != s[i - 1]:
			l.append(1 + l[-1])
		else:
			l.append(l[-1])
	ans = 0
	for i in range(k, n):
		ans += l[i] - l[i - k]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(input())
	val = [0] * n
	val[0] = 1
	for i in range(1, n):
		if l[i] != l[i - 1]:
			val[i] = val[i - 1] + 1
		else:
			val[i] = val[i - 1]
	ans = 0
	for i in range(0, n - k, 1):
		ans += val[i + k] - val[i]
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	(tot, prev) = (0, 0)
	i = 1
	wind = 0
	while i < n:
		if i == 1 and wind == 0:
			for j in range(i, i + k):
				if s[j] != s[j - 1]:
					tot += 1
			i += k
			wind += 1
			prev = tot
		else:
			init = tot
			if s[wind] != s[wind - 1]:
				tot += prev - 1
			else:
				tot += prev
			if s[i] != s[i - 1]:
				tot += 1
			prev = tot - init
			wind += 1
			i += 1
	print(tot)