You may have solved a lot of problems related to XOR and we are sure that you liked them, so here is one more problem for you.

You are given a binary string S of length N. Let string T be the result of taking the XOR of all substrings of size K of S. You need to find the number of 1 bits in T.

Note:
A substring is a continuous part of string which can be obtained by deleting some (may be none) character's from the beginning and some (may be none) character's from the end.
XOR of many similar-sized strings is defined [here].

------ Input Format ------ 

- The first line of the input contains an integer T - the number of test cases. The test cases then follow.
- The first line of each test case contains two integers N and K.
- The second line of each test case contains a binary string S of size N.

------ Output Format ------ 

For each test case, output on a single line number of 1 bits in the XOR of all substrings of size K of S.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ K ≤N ≤ 2 \cdot 10^{5}$
$|S| = N$
$S$ only contains characters 0 and 1.

----- Sample Input 1 ------ 
4
4 1
1010
4 2
1001
4 3
1111
4 4
0110

----- Sample Output 1 ------ 
0
2
0
2

----- explanation 1 ------ 
- Test case $1$: All $1$-sized substrings of $S$ are:
- 0
- 1
- 1
- 0

The XOR of these strings is 0, therefore the number of 1 bits is $0$.
- Test case $2$: All $2$-sized substrings of $S$ are:
- 10
- 00
- 01

The XOR of these strings is 11, therefore the number of 1 bits is $2$.
- Test case $3$: All $3$-sized substrings of $S$ are:
- 111
- 111

The XOR of these strings is 000, therefore the number of 1 bits is $0$.
- Test case $4$: All $4$-sized substrings of $S$ are:
- 0110

The XOR of these strings is 0110, therefore the number of 1 bits is $2$.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

String algorithms

Range queries

Mathematics

Data structures
Skill types: Bit manipulation

Data structures

Range queries

Starter code:

Solutions:
def Test(n, a, k):
	dp = [0] * n
	dp[0] = a[0]
	for i in range(1, n):
		dp[i] = dp[i - 1] + a[i]
	s = [0] * k
	r = 0
	for i in range(k):
		s[i] = dp[n - k + i] - r & 1
		r = dp[i]
	return s.count(1)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, [*input()]))
	print(Test(n, a, k))


from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, [*input()]))
	q = [0] * n
	q[0] = a[0]
	for i in range(1, n):
		q[i] = q[i - 1] + a[i]
	w = [0] * k
	r = 0
	for i in range(k):
		w[i] = q[n - k + i] - r & 1
		r = q[i]
	print(w.count(1))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = input()
	nbo = 0
	k1 = arr[0:n - k + 1].count('1')
	if k1 % 2 == 1:
		nbo += 1
	for i in range(1, k):
		k1 += int(arr[n - k + 1 + i - 1]) - int(arr[i - 1])
		if k1 % 2 == 1:
			nbo += 1
	print(nbo)


import math, sys, collections
input = sys.stdin.readline
istr = lambda : input().strip()
inum = lambda : int(input().strip())
imap = lambda : map(int, input().strip().split())
ilist = lambda : list(map(int, input().strip().split()))
try:
	tcs = inum()
	for i in range(tcs):
		(n, k) = imap()
		s = istr()
		w = '$'
		w += s
		res = 0
		presum = [0] * (n + 2)
		for i in range(1, n + 1):
			presum[i] = presum[i - 1] + (w[i] == '1')
		for i in range(1, k + 1):
			(start, end) = (i, n - k + i)
			val = presum[end] - presum[start - 1]
			res += val % 2
		print(res)
except Exception as e:
	pass


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	K = n - k + 1
	xor = 0
	ans = 0
	for (i, char) in enumerate(s):
		xor ^= int(char)
		if i >= K - 1:
			if xor:
				ans += 1
			xor ^= int(s[i - K + 1])
	print(ans)


T = int(input())
for _ in range(T):
	(n, k) = input().split()
	s = input()
	n = int(n)
	k = int(k)
	ans = 0
	c = 0
	for i in range(0, n - k):
		if s[i] == '1':
			c += 1
	for j in range(0, k):
		if s[n - k + j] == '1':
			c += 1
		if c % 2 != 0:
			ans += 1
		if s[j] == '1':
			c -= 1
	print(ans)


def xor(n, k, s):
	count = 0
	if n == k:
		for i in s:
			if i == '1':
				count += 1
		return count
	temp = 0
	for i in range(n - k + 1):
		if s[i] == '1':
			temp += 1
	if temp & 1:
		count += 1
	for i in range(1, k):
		if s[i - 1] == '1':
			temp -= 1
		if s[n - k + i] == '1':
			temp += 1
		if temp & 1:
			count += 1
	return count
t = int(input().strip())
while t:
	(N, K) = map(int, input().split())
	S = input()
	print(xor(N, K, S))
	t -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = []
	c = 0
	for j in s:
		if j == '1':
			c = c + 1
		l.append(c)
	x = n - k
	t = [0] * k
	p = x + 1
	t[0] = l[p - 1]
	for j in range(1, k):
		t[j] = l[j + p - 1] - l[j - 1]
	c = 0
	for j in t:
		if j % 2 == 1:
			c = c + 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	if k == 1:
		cnt = s.count('1')
		if cnt % 2 == 0:
			print('0')
		else:
			print('1')
	else:
		for i in range(n - k + 1):
			if s[i] == '1':
				count += 1
		lst = []
		lst.append(count)
		p = n - k + 1
		start = 0
		while p < n:
			if s[start] == '1':
				count = count - 1
			if s[p] == '1':
				count = count + 1
			start += 1
			p += 1
			lst.append(count)
		ans = 0
		for i in lst:
			if i % 2 != 0:
				ans += 1
		print(ans)


for _ in range(int(input())):

	def xor(x, y):
		if x == '0' and y == '0' or (x == '1' and y == '1'):
			return '0'
		else:
			return '1'
	(N, K) = map(int, input().split())
	S = input()
	ans = 0
	m = len(S[:N - K + 1].replace('0', ''))
	prev = 'even'
	if m % 2 != 0:
		ans = 1
		prev = 'odd'
	for i in range(1, K):
		if S[i - 1] == '1' and S[i + N - K] == '1':
			if prev == 'odd':
				ans += 1
		elif S[i - 1] == '0' and S[i + N - K] == '0':
			if prev == 'odd':
				ans += 1
		elif S[i - 1] == '0' and S[i + N - K] == '1':
			if prev == 'even':
				prev = 'odd'
				ans += 1
			elif prev == 'odd':
				prev = 'even'
		elif prev == 'even':
			prev = 'odd'
			ans += 1
		elif prev == 'odd':
			prev = 'even'
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	r = ''
	h = {'1': 0, '0': 0}
	j = 0
	for i in range(n):
		if i <= n - k:
			h[s[i]] += 1
		else:
			if h['1'] % 2:
				r += '1'
			else:
				r += '0'
			h[s[i]] += 1
			h[s[j]] -= 1
			j = j + 1
	if h['1'] % 2:
		r = r + '1'
	c = 0
	for i in r:
		if i == '1':
			c = c + 1
	print(c)


def func():
	(n, k) = map(int, input().split())
	c = 0
	ans = 0
	s = input()
	for i in range(n - k + 1):
		if s[i] == '1':
			c += 1
	if c % 2 == 1:
		ans += 1
	for i in range(n - k + 1, n):
		if s[i - n + k - 1] == '1':
			c -= 1
		if s[i] == '1':
			c += 1
		if c % 2 == 1:
			ans += 1
	print(ans)
t = int(input())
for i in range(t):
	func()


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

def main():
	x = getInput()
	y = input()
	res = 0
	p = 0
	q = x[0] - x[1] + 2
	flag = 0
	if y[:q - 1].count('1') % 2 != 0:
		res += 1
		flag = 1
	while q <= x[0]:
		if y[p] != y[q - 1]:
			flag = (flag + 1) % 2
		if flag == 1:
			res += 1
		p += 1
		q += 1
	print(res)
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	xo = 0
	for i in range(n - k + 1):
		xo ^= int(s[i])
	if xo == 1:
		ans += 1
	ibeg = 0
	iend = n - k + 1
	while iend < n:
		xo ^= int(s[ibeg])
		xo ^= int(s[iend])
		iend += 1
		ibeg += 1
		if xo == 1:
			ans += 1
	print(ans)


from sys import stdin

def check(n, k, s):
	ans = 0
	c = 0
	for i in range(0, n - k):
		if s[i] == '1':
			c += 1
	for i in range(0, k):
		if s[n - k + i] == '1':
			c += 1
		if c % 2 != 0:
			ans += 1
		if s[i] == '1':
			c -= 1
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(check(n, k, s))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = []
	p = 0
	for i in range(n - k + 1):
		p = p ^ int(s[i])
	ans.append(p)
	i = 0
	j = n - k + 1
	while j < n:
		p = p ^ int(s[i])
		p = p ^ int(s[j])
		i += 1
		j += 1
		ans.append(p)
	print(ans.count(1))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	xo = 0
	c = 0
	for i in range(n - k + 1):
		xo ^= int(s[i])
	if xo == 1:
		c += 1
	inc = n - k + 1
	exc = 0
	while inc < n:
		xo ^= int(s[exc])
		xo ^= int(s[inc])
		exc += 1
		inc += 1
		if xo == 1:
			c += 1
	print(c)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	lst = list(map(int, input().split()))
	s = input()
	(n, k) = (lst[0], lst[1])
	lr = [0] * (n + 1)
	rl = [0] * (n + 1)
	l = '$' + s
	for i in range(1, n + 1):
		if l[i] == '1':
			lr[i] = lr[i - 1] + 1
		else:
			lr[i] = lr[i - 1]
	r = s + '$'
	for i in range(n - 1, -1, -1):
		if r[i] == '1':
			rl[i] = rl[i + 1] + 1
		else:
			rl[i] = rl[i + 1]
	lr = lr[1:]
	rl = rl[:-1]
	ones = lr[-1]
	ln = n - k + 1
	i = 0
	ans = 0
	while True:
		end = i + ln - 1
		if end >= n:
			break
		else:
			one = ones
			if i > 0:
				one -= lr[i - 1]
			if end < n - 1:
				one -= rl[end + 1]
			if one % 2 != 0:
				ans += 1
		i += 1
	print(ans)


from functools import reduce
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	count = 0
	if n == k:
		print(s.count('1'))
	else:
		s1 = []
		for c in s:
			s1.append(int(c))
		test = s1[:n - k + 1]
		j = len(test)
		i = 0
		res = reduce(lambda x, y: x ^ y, test)
		while True:
			if res == 1:
				count += 1
			if j < n:
				res = res ^ s1[i] ^ s1[j]
				i += 1
				j += 1
			else:
				break
		print(count)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = input()
	B = [0] * (n + 1)
	for (i, val) in enumerate(A, start=1):
		if val == '0':
			B[i] = B[i - 1]
		else:
			B[i] = B[i - 1] + 1
	ans = 0
	for i in range(k):
		ans += (B[n - k + i + 1] - B[i]) % 2
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(input())
	ans = [0] * (n + 1)
	c = 0
	for i in range(n):
		c += int(li[i])
		ans[i + 1] = c
	t = 0
	for i in range(1, k + 1):
		if (ans[i + n - k] - ans[i - 1]) % 2 == 1:
			t += 1
	print(t)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	xor = input()
	prefix = [0] * n
	prefix[-1] = 1 if xor[-1] == '1' else 0
	for i in range(n - 2, -1, -1):
		prefix[i] = prefix[i + 1] + 1 if xor[i] == '1' else prefix[i + 1]
	prefix.append(0)
	ans = 0
	for i in range(m):
		if (prefix[i] - prefix[n - m + i + 1]) % 2:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	s = [int(x) for x in s]
	ans = 0
	tmp = 0
	for i in range(0, n - k + 1):
		tmp = tmp ^ s[i]
	ans += tmp
	for i in range(n - k + 1, n):
		tmp = tmp ^ s[i - (n - k + 1)]
		tmp = tmp ^ s[i]
		ans += tmp
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	data = list(map(int, input()))
	pre = [0] * (len(data) + 1)
	for i in range(len(data)):
		pre[i + 1] = pre[i] + data[i]
	total = 0
	col_length = len(data) - k + 1
	for i in range(k):
		count = pre[i + col_length] - pre[i]
		total += count % 2
	print(total)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	s = input()
	pointer = 0
	c = 0
	y = int(s[0])
	for i in range(1, n - k + 1):
		y = y ^ int(s[i])
	if y == 1:
		c = c + 1
	pointer = 0
	for i in range(n - k + 1, n):
		y = y ^ int(s[pointer])
		y = y ^ int(s[i])
		pointer = pointer + 1
		if y == 1:
			c = c + 1
	print(c)


for t in range(int(input())):
	(N, K) = map(int, input().split())
	S = str(input())
	prefixCount = [0]
	for i in range(N):
		if S[i] == '1':
			prefixCount.append(prefixCount[-1] + 1)
		else:
			prefixCount.append(prefixCount[-1])
	count = 0
	for i in range(K):
		if (prefixCount[i] - prefixCount[N - K + 1 + i]) % 2 != 0:
			count += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	if n == k:
		print(s.count(1))
	else:
		a = [0]
		temp = 0
		for i in s:
			a.append(temp + i)
			temp += i
		x = n - k + 1
		set_bits = 0
		for i in range(k):
			ones = a[i + x] - a[i]
			if ones & 1:
				set_bits += 1
		print(set_bits)


import sys
from itertools import accumulate
from operator import xor
i = iter(sys.stdin)
next(i)
for (t, s) in zip(i, i):
	(n, k) = map(int, t.split())
	a = (0, *accumulate(map(int, s[:-1]), xor))
	print(sum((x ^ y for (x, y) in zip(a, a[n - k + 1:]))))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	o = 0
	t = 0
	last = 0
	for j in range(n - k + 1):
		t += 1 if s[j] == '1' else 0
		last = t & 1
		o = last
	for i in range(1, k):
		if s[i - 1] != s[n - k + i]:
			last ^= 1
		o += last
	print(o)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = input()
	c = 0
	ans = 0
	for i in range(n - k + 1):
		if A[i] == '1':
			c += 1
	if c % 2 == 1:
		ans += 1
	beg = 0
	end = n - k + 1
	while end < n:
		if A[beg] == '1':
			c -= 1
		if A[end] == '1':
			c += 1
		if c % 2 == 1:
			ans += 1
		beg += 1
		end += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().rstrip()
	if n == k:
		print(s.count('1'))
	else:
		c = d = 0
		for i in range(0, n - k + 1):
			if s[i] == '1':
				c += 1
		if c % 2 != 0 and c > 0:
			d += 1
		for i in range(n - k + 1, n):
			if s[i - n + k - 1] == '1' and s[i] == '0':
				c -= 1
			elif s[i - n + k - 1] == '0' and s[i] == '1':
				c += 1
			if c % 2 != 0 and c > 0:
				d += 1
		print(d)


def do(a, n, k):
	l = n - k + 1
	counter = 0
	c = 0
	for i in range(l):
		c ^= a[i]
	if c == 1:
		counter += 1
	(p, q) = (0, l)
	for i in range(k - 1):
		c ^= a[p + i]
		c ^= a[q + i]
		if c == 1:
			counter += 1
	print(counter)
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = input()
	a = [int(i) for i in a]
	do(a, n, k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	pref = []
	m = 0
	for i in range(n):
		if s[i] == '1':
			m += 1
		pref.append(m)
	ans = 0
	i = 1
	while k > 0:
		if k - 2 >= 0:
			p = pref[-i] - pref[k - 2]
			if p % 2 != 0:
				ans += 1
		else:
			p = pref[-i]
			if p % 2 != 0:
				ans += 1
		i = i + 1
		k = k - 1
	print(ans)


import collections
import sys
from collections import OrderedDict, Counter, defaultdict
import math
import bisect
from sys import stdin, stdout

def with_index():
	a = []
	i = 0
	for t in map(int, input().split()):
		a.append((t, i))
		i += 1
	return a

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

def in1():
	return int(input())

def take_input():
	return stdin.readline()

def display_arr(arr):
	stdout.write(' '.join(map(str, arr)) + '\n')

def display_num(num):
	stdout.write(str(num) + '\n')

def factorial(n):
	return n * factorial(n - 1) if n > 1 else 1

def percent(c, s):
	return c / s * 100

def l2d(a):
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	return d
a = []

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)

def sol(code, chef):
	if not code or not chef:
		return 'WA'
	elif len(code) != len(chef):
		return 'WA'
	n = len(code)
	for i in range(n):
		if code[i] > chef[i]:
			return 'WA'
	return 'AC'

def get_substr(s):
	(code, chef) = ([], [])
	for i in range(n - 3):
		if s[i] != 'c':
			continue
		sub = ''
		for j in range(i, n - 3):
			sub += s[j]
for _ in range(in1()):
	(n, k) = get_line()
	s = input()
	xo = 0
	ans = 0
	for i in range(n - k + 1):
		xo ^= int(s[i])
	if xo == 1:
		ans += 1
	i = 0
	j = n - k + 1
	while j < n:
		xo = xo ^ int(s[i])
		xo = xo ^ int(s[j])
		i += 1
		j += 1
		if xo == 1:
			ans += 1
	print(ans)


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


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		xor = 0
		for i in range(n - k + 1):
			xor = xor ^ int(s[i])
		cnt = 0
		if xor == 1:
			cnt += 1
		for i in range(1, k):
			xor = xor ^ int(s[i - 1]) ^ int(s[n - k + i])
			if xor == 1:
				cnt += 1
		print(cnt)
except:
	pass


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


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().strip().split()]
	s = list(input().strip())
	ans = [int(x) for x in s[:k]]
	for j in range(1):
		for l in range(j + 1, n - k + 1 + j):
			ans[j] = int(ans[j]) ^ int(s[l])
	for j in range(1, k):
		ans[j] = ans[j - 1] ^ int(s[j - 1]) ^ int(s[n - k + j])
	print(sum(ans))


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
from random import randint
import math
import sys
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	a = [int(s[i]) for i in range(n)]
	p = [0 for i in range(n + 1)]
	p[1] = a[0]
	for i in range(2, n + 1):
		p[i] = p[i - 1] + a[i - 1]
	final = [0 for i in range(k)]
	for i in range(0, k):
		final[i] = (p[n - k + i + 1] - p[i]) % 2
	print(sum(final))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	answer = 0
	for i in range(n - k):
		if s[i] == '1':
			c += 1
	for i in range(k):
		if s[n - k + i] == '1':
			c += 1
		if c % 2 != 0:
			answer += 1
		if s[i] == '1':
			c -= 1
	print(answer)


t = int(input())
for a in range(0, t):
	(x, y) = [int(x) for x in input().split()]
	s = input()
	ans = 0
	c = 0
	for i in range(0, x - y):
		if s[i] == '1':
			c += 1
	for i in range(0, y):
		if s[x - y + i] == '1':
			c += 1
		if c % 2 != 0:
			ans += 1
		if s[i] == '1':
			c -= 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().strip()
	a = [int(s[i]) for i in range(n)]
	p = [0 for i in range(n + 1)]
	p[1] = a[0]
	for i in range(2, n + 1):
		p[i] = p[i - 1] + a[i - 1]
	final = [0 for i in range(k)]
	for i in range(1, k + 1):
		final[i - 1] = (p[n - k + i] - p[i - 1]) % 2
	print(sum(final))


try:
	t = int(input())
	for i in range(t):
		(n, k) = list(map(int, input().split()))
		s = input()
		answer = 0
		c = 0
		for i in range(n - k):
			if s[i] == '1':
				c = c + 1
		for i in range(k):
			if s[n - k + i] == '1':
				c = c + 1
			if c % 2 != 0:
				answer = answer + 1
			if s[i] == '1':
				c = c - 1
		print(answer)
except:
	pass


for i in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	res = 0
	ginti = 0
	for i in range(N - K):
		if S[i] == '1':
			ginti += 1
	for i in range(K):
		if S[N - K + i] == '1':
			ginti += 1
		if ginti % 2 != 0:
			res += 1
		if S[i] == '1':
			ginti -= 1
	print(res)


for j in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	o = [0] * (n + 1)
	for i in range(n):
		if s[i] == '1':
			o[i + 1] = o[i] + 1
		else:
			o[i + 1] = o[i]
	s = 0
	for i in range(k):
		oo = o[i + (n - k + 1)] - o[i]
		if oo % 2 == 1:
			s += 1
	print(s)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	s = input()
	arr = [0] * N
	add = 0
	for i in range(N):
		if s[i] == '1':
			add += 1
		arr[i] = add
	x = N - K
	ans = [0] * K
	p = x + 1
	ans[0] = arr[p - 1]
	for i in range(1, K):
		ans[i] = arr[i + p - 1] - arr[i - 1]
	count = 0
	for i in range(K):
		if ans[i] % 2 == 1:
			count += 1
	print(count)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	set_bit = 0
	for i in range(n - k + 1):
		if s[i] == '1':
			set_bit = set_bit + 1
	count = 0
	if set_bit % 2 == 0:
		count = 0
	else:
		count = 1
	h = n - k + 1
	l = 0
	for i in range(0, k - 1):
		if h < n and s[l] != s[h]:
			set_bit = set_bit - 1
		if set_bit % 2 != 0:
			count = count + 1
		h = h + 1
		l = l + 1
	print(count)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	d = dict()
	m = [0] * (n + 1)
	for r in range(n):
		if s[r] == '1':
			m[r + 1] = 1
	for r in range(1, n + 1):
		m[r] += m[r - 1]
	for r in range(k):
		if (m[n - k + r + 1] - m[r]) % 2 == 1:
			l += 1
	print(l)


def againxor(n, k, s):
	count = 0
	s = '&' + s
	dp = [0 for i in range(n + 2)]
	for i in range(1, n + 1):
		dp[i] = dp[i - 1] + int(s[i] == '1')
	for i in range(1, k + 1):
		start = i
		end = n - k + i
		value = dp[end] - dp[start - 1]
		count += value % 2
	return count
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(againxor(n, k, s))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	ll = list(map(int, s))
	c1 = 0
	arr = [0] * n
	for i in range(n):
		if ll[i] == 1:
			c1 += 1
		arr[i] = c1
	x = n - k
	ans = ['\n'] * k
	ans[0] = arr[x]
	for i in range(1, k, 1):
		ans[i] = arr[i + x] - arr[i - 1]
	res = 0
	for i in range(k):
		if ans[i] % 2 != 0:
			res += 1
	print(res)
	t -= 1


import math
from collections import Counter

def calc_slow(data, k):
	result = 0
	for i in range(0, len(data) - k + 1):
		num = int(data[i:i + k], 2)
		result ^= num
	return str(bin(result)).count('1')

def calc_fast(data, k):
	result = 0
	slide = 0
	for i in range(len(data)):
		slide += int(data[i])
		if i >= len(data) - k:
			result += slide % 2
			slide -= int(data[i - (len(data) - k)])
	return result
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	data = input()
	print(calc_fast(data, k))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = [int(e) for e in input()]
	pref = [0] * n
	pref[0] = s[0]
	for i in range(1, n):
		pref[i] = pref[i - 1] + s[i]
	count = 0
	if pref[n - k] % 2 != 0:
		count += 1
	for i in range(1, k):
		val = pref[n - k + i] - pref[i - 1]
		if val % 2 != 0:
			count += 1
	print(count)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = [0] * n
	sum = 0
	for i in range(n):
		if s[i] == '1':
			sum += 1
		a[i] = sum
	x = n - k
	p = x + 1
	ans = [0] * k
	ans[0] = a[p - 1]
	for i in range(1, k):
		ans[i] = a[i + p - 1] - a[i - 1]
	count = 0
	for i in range(k):
		if ans[i] % 2 == 1:
			count += 1
	print(count)


t = int(input())
for u in range(t):
	(n, k) = map(int, input().split())
	s = input()
	sum = 0
	a = []
	for i in range(n):
		if s[i] == '1':
			sum = sum + 1
		a.append(sum)
	p = n - k + 1
	ans = []
	ans.append(a[p - 1])
	for i in range(1, k):
		ans.append(a[i + p - 1] - a[i - 1])
	c = 0
	for i in range(k):
		if ans[i] % 2 == 1:
			c = c + 1
	print(c)


for case in range(int(input())):
	(n, k) = map(int, input().split())
	s = [int(i) for i in input()]
	sm = sum(s[0:n - k + 1])
	c = sm % 2
	for i in range(1, k):
		sm = sm - s[i - 1] + s[n - k + i]
		c += sm % 2
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	li = [0] * n
	if s[0] == '1':
		li[0] = 1
	for i in range(1, n):
		if s[i] == '1':
			li[i] = li[i - 1] + 1
		else:
			li[i] = li[i - 1]
	cnt = 0
	x = n - k
	if li[x] % 2:
		cnt += 1
	for i in range(1, k):
		if (li[i + x] - li[i - 1]) % 2:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	pre = [0]
	(n, k) = map(int, input().split())
	s = input()
	pre[0] = int(s[0])
	for i in range(1, n):
		pre.append(pre[i - 1] + int(s[i]))
	ans = pre[n - k] % 2
	for i in range(1, k):
		ans += (pre[n - k + i] - pre[i - 1]) % 2
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input()))
	cnt = 0
	s = ''
	for x in range(n - k + 1):
		cnt ^= lst[x]
	s += str(cnt)
	for x in range(n - k + 1, n):
		cnt ^= lst[x - (n - k + 1)]
		cnt ^= lst[x]
		s += str(cnt)
	print(s.count('1'))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	sum = 0
	l = []
	for j in range(n):
		if s[j] == '1':
			sum += 1
		l.append(sum)
	x = n - k
	ans = [0] * k
	p = x + 1
	ans[0] = l[p - 1]
	for j in range(1, k, 1):
		ans[j] = l[j + p - 1] - l[j - 1]
	count = 0
	for j in range(k):
		if ans[j] % 2 == 1:
			count += 1
	print(count)


T = int(input())
for _ in range(T):
	[N, K] = list(map(int, input().rstrip().split()))
	binstring = input()
	num = []
	base = binstring[:K]
	basenum = int(base, 2)
	left = 0
	minus = 2 ** (K - 1)
	temp = basenum
	ans = basenum
	for j in range(K, N):
		if binstring[left] == '1':
			temp -= minus
		temp = 2 * temp
		if binstring[j] == '1':
			temp += 1
		ans = ans ^ temp
		left += 1
	print(bin(ans).count('1'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = 0
	l = [0] * n
	for i in range(n):
		if s[i] == '1':
			c += 1
		l[i] = c
	u = n - k
	lol = 0
	g = l[u]
	if g % 2 == 1:
		lol += 1
	for i in range(k - 1):
		g = l[i + u + 1] - l[i]
		if g % 2 == 1:
			lol += 1
	print(lol)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	L = [0] * N
	X = 0
	for i in range(N):
		if S[i] == '1':
			X += 1
		L[i] = X
	M = [0] * K
	M[0] = L[N - K]
	for i in range(1, K):
		M[i] = L[i + N - K] - L[i - 1]
	ctr = 0
	for i in range(K):
		if M[i] % 2 == 1:
			ctr += 1
	print(ctr)


test = int(input())
while test:
	(n, k) = map(int, input().split())
	s = input()
	i = 0
	j = n - k
	c = 0
	count = s.count('1', i, j + 1)
	for i in range(k):
		if count % 2 != 0:
			c += 1
		if s[i] == '1':
			count -= 1
		i -= 1
		j += 1
		if j < len(s) and s[j] == '1':
			count += 1
	print(c)
	test -= 1


n = int(input())
for _ in range(n):
	(N, K) = map(int, input().split())
	S = str(input())
	sum = 0
	arr = [0] * N
	ans = [0] * K
	for i in range(0, N):
		if S[i] == '1':
			sum = sum + 1
		arr[i] = sum
	x = N - K
	p = x + 1
	ans[0] = arr[p - 1]
	for i in range(1, K):
		ans[i] = arr[i + p - 1] - arr[i - 1]
	c = 0
	for i in range(0, K):
		if ans[i] % 2 == 1:
			c = c + 1
	print(c)


for _ in range(int(input())):
	(l, k) = list(map(int, input().split(' ')))
	s = input()
	subs = len(s) - (k - 1)
	presum = [0] if s[0] == '0' else [1]
	for i in range(1, len(s)):
		presum.append(presum[i - 1] + (0 if s[i] == '0' else 1))
	c = 0
	for i in range(k):
		ts = s[i:i + subs]
		ans = presum[i + subs - 1] - (presum[i - 1] if i - 1 >= 0 else 0)
		if ans & 1 != 0:
			c += 1
	print(c)


tc = int(input())
arr = []
for i in range(tc):
	s = input().split()
	msize = int(s[0])
	subsize = int(s[1])
	m = input()
	count = 0
	result = int(m[0])
	for j in range(1, msize - subsize + 1):
		result = result ^ int(m[j])
	if result == 1:
		count = count + 1
	for j in range(subsize - 1):
		result = result ^ int(m[j])
		result = result ^ int(m[j + msize - subsize + 1])
		if result == 1:
			count = count + 1
	arr.append(count)
for i in arr:
	print(i)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if n == k:
		x = 0
		for i in s:
			if i == '1':
				x += 1
		print(x)
		continue
	window = n - k + 1
	ones = 0
	x = 0
	for i in range(window):
		if s[i] == '1':
			x += 1
	if x % 2 == 1:
		ones += 1
	for i in range(k - 1):
		if s[i] == '1':
			x -= 1
		if s[window + i] == '1':
			x += 1
		if x % 2 == 1:
			ones += 1
	print(ones)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	if n - k == 0:
		ans = s.count('1')
	else:
		a = int(s[0])
		for j in range(n - k):
			a = a ^ int(s[j + 1])
		ans = a
		for j in range(k - 1):
			if s[j] != s[j + n - k + 1]:
				if a == 1:
					a = 0
				else:
					a = 1
			ans += a
	print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	binn = '$' + input()
	lll = [0] * (x + 2)
	for i in range(1, x + 1):
		if binn[i] == '1':
			lll[i] = lll[i - 1] + 1
		else:
			lll[i] = lll[i - 1]
	ansss = 0
	for i in range(1, y + 1):
		ansss += (lll[x - y + i] - lll[i - 1]) % 2
	print(ansss)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	arr = [0] * n
	sm = 0
	for i in range(n):
		if s[i] == '1':
			sm += 1
		arr[i] = sm
	x = n - k
	ans = [0] * k
	p = x + 1
	ans[0] = arr[p - 1]
	for i in range(1, k):
		ans[i] = arr[i + p - 1] - arr[i - 1]
	cnt = 0
	for i in ans:
		if i % 2 != 0:
			cnt += 1
	print(cnt)


import sys
from itertools import islice
i = iter(sys.stdin)
next(i)
for (t, s) in zip(i, i):
	(n, k) = map(int, t.split())
	a = [0]
	for x in islice(s, n):
		a.append(a[-1] ^ (x > '0'))
	print(sum((x ^ y for (x, y) in zip(a, a[n - k + 1:]))))