For a binary string A, let f(A) denote its *badness*, defined to be the difference between the number of zeros and number of ones present in it. That is, if the string has c_{0} zeros and c_{1} ones, its badness is |c_{0} - c_{1}|. For example, the badness of "01" is |1 - 1| = 0, the badness of "100" is |2 - 1| = 1, the badness of "1101" is |1 - 3| = 2, and the badness of the empty string is |0 - 0| = 0.

You are given an integer N and a binary string S. 

You would like to partition S into K disjoint [subsequences] (some of which may be empty), such that the maximum badness among all these K subsequences is minimized. Find this value.

Formally,
Let S_{1}, S_{2}, \ldots, S_{K} be a partition of S into disjoint subsequences. Every character of S must appear in one of the S_{i}. Some of the S_{i} may be empty.
Then, find the *minimum* value of \max(f(S_{1}), f(S_{2}), \ldots, f(S_{K})) across all possible choices of S_{1}, S_{2}, \ldots, S_{K} satisfying the first condition.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The description of each test case is as follows: 
- The first line contains two space-separated integers N and K.
- The second line contains the binary string S of length N.

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

​For each test case, print the minimum possible value of the maximum badness when S is partitioned into K subsequences.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ K ≤ 10^{9}$
$S$ is a binary string, i.e, contains only the characters $0$ and $1$
- The sum of $N$ across all test cases doesn't exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
7 5
1010100
4 1
1100
6 2
101111
----- Sample Output 1 ------ 
1
0
2
----- explanation 1 ------ 
Test case $1$: Let's take a couple of examples.
- Suppose the partition is $\{"10", "10", "0", "10", "\ "\}$, obtained as $\textcolor{red}{10}\textcolor{blue}{10}\textcolor{orange}{10}0$ (elements of one color form a subsequence). The respective badness values are $\{0, 0, 1, 0, 0\}$, the maximum of which is $1$.
- Suppose the partition is $\{"101", "00", "\ ", "10", "\ "\}$, obtained as $\textcolor{red}{10}10\textcolor{red}{1}\textcolor{blue}{00}$. The respective badness values are $\{1, 2, 0, 0, 0\}$, the maximum of which is $2$.

The first partition, with a maximum badness of $1$, is one of the optimal partitions.

Test case $2$: The only possible partition is $\{"1100"\}$, which has a badness of $0$.

Test case $3$: The partitions $\{"1011", "11"\}$ and $\{"0111", "11"\}$ both lead to a badness of $\max(2, 0) = 2$, which is the minimum possible.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
import math

def badness(s):
	return abs(s.count('0') - s.count('1'))

def bp():
	return int(input())

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

def ls():
	return list(map(int, input().split()))
t = int(input())
for i in range(t):
	(n, k) = ip()
	s = input()
	print(math.ceil(badness(s) / k))


t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	z = 0
	o = 0
	for j in input():
		if j == '0':
			z += 1
		else:
			o += 1
	ans = -(abs(z - o) // -k)
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	bad = abs(s.count('1') - s.count('0'))
	print(math.ceil(bad / k))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = input()
	c0 = c1 = 0
	for i in a:
		if i == '1':
			c1 += 1
		else:
			c0 += 1
	k1 = max(c1, c0) - min(c1, c0)
	g = k1 // k
	a1 = g + (1 if k1 % k != 0 else 0)
	print(a1)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = input()
	co = 0
	cz = 0
	for i in arr:
		if i == '1':
			co += 1
		else:
			cz += 1
	bad = abs(cz - co)
	if bad == 0:
		print(0)
	elif bad % k == 0:
		print(bad // k)
	elif bad % k != 0:
		print(bad // k + 1)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	o = 0
	z = 0
	for i in s:
		if i == '0':
			z += 1
		else:
			o += 1
	l = abs(z - o)
	m = int(math.ceil(l / k))
	print(m)


import math
x = int(input())
for i in range(x):
	(n, k) = list(map(int, input().split()))
	s = input()
	zeros = s.count('0')
	ones = n - zeros
	diff = zeros - ones
	print(math.ceil(abs(diff) / k))


from math import ceil
t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	a = s.count('1')
	b = n - a
	c = abs(b - a)
	print(ceil(c / k))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	o = s.count('0')
	z = n - o
	if o < z:
		(o, z) = (z, o)
	print((o - z) // k + bool((o - z) % k))


import math
a = int(input())
for _ in range(a):
	(n, k) = map(int, input().split())
	arr = list(input())
	a1 = arr.count('1')
	a0 = n - a1
	x = math.ceil(abs(a0 - a1) / k)
	print(x)


from math import ceil
try:
	n = int(input())
	for j in range(n):
		(a, b) = map(int, input().split())
		l = list(input())
		p = abs(l.count('0') - l.count('1'))
		print(ceil(p / b))
except:
	pass


T = int(input())
while T > 0:
	(n, k) = map(int, input().split())
	s = input()
	zeros = s.count('0')
	ones = s.count('1')
	s_ = abs(zeros - ones)
	if s_ >= k:
		if s_ % k == 0:
			print(s_ // k)
		else:
			print(s_ // k + 1)
	elif s_ != 0:
		print(1)
	else:
		print(0)
	T -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = None
	z = s.count('0')
	o = s.count('1')
	d = abs(z - o)
	if d == 0:
		a = 0
	if a == None and k >= d:
		a = 1
	elif a == None:
		a = d // k if d % k == 0 else d // k + 1
	print(a)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	s = [x for x in input()]
	m = len(s) - 2 * min(s.count('0'), s.count('1'))
	badness = 0
	while m - k >= 0:
		m -= k
		badness += 1
	if m > 0:
		badness += 1
	print(badness)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = None
	zeros = s.count('0')
	ones = s.count('1')
	diff = abs(zeros - ones)
	if diff == 0:
		ans = 0
	if ans == None and k >= diff:
		ans = 1
	elif ans == None:
		if diff % k == 0:
			ans = diff // k
		else:
			ans = diff // k + 1
	print(ans)


while True:
	try:
		for _ in range(int(input())):
			(x, y) = map(int, input().split())
			s = input()
			(one, zero) = (0, 0)
			for i in s:
				if i == '1':
					one += 1
				else:
					zero += 1
			m = abs(one - zero)
			if m % y != 0:
				print(m // y + 1)
			else:
				print(m // y)
	except EOFError:
		break


from math import ceil
for i in range(int(input())):
	ans = 0
	(n, k) = map(int, input().split())
	s = input()
	count0 = s.count('0')
	count1 = s.count('1')
	ans = abs(count0 - count1)
	ans = ceil(ans / k)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	d = abs(string.count('0') - string.count('1'))
	if d:
		predicting_answer = d // k
		if d % k == 0:
			print(predicting_answer)
		else:
			print(predicting_answer + 1)
	else:
		print(0)


for i in range(int(input())):
	(N, K) = map(int, input().split(' '))
	s = str(input())
	min1 = min(s.count('0'), s.count('1'))
	max1 = max(s.count('0'), s.count('1'))
	num = max1 - min1
	if num == 0:
		print(0)
	else:
		div = num // K
		rem = num % K
		if rem == 0:
			print(div)
		else:
			print(div + 1)


for i in range(int(input())):
	(a, k) = map(int, input().split())
	s = input()
	l = list(s)
	c0 = l.count('0')
	c1 = l.count('1')
	diff = abs(c0 - c1)
	if diff % k == 0:
		print(diff // k)
	else:
		print(diff // k + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	o = s.count('1')
	z = n - o
	print(-(-abs(z - o) // k))


import math, re

def getMaxBadness(S: str, K: int) -> int:
	try:
		c_0 = S.count('0')
		c_1 = S.count('1')
		B = math.ceil(abs(c_0 - c_1) / K)
		return B
	except Exception as e:
		raise Exception('getMaxBadness: ' + str(e))
T = int(input())
try:
	for i in range(T):
		(N, K) = map(int, input().split(' '))
		S = str(input())
		if N < 1 or N > 2 * 10 ** 5:
			raise Exception('Input out of range (N): {}'.format(str(N)))
		if K < 1 or K > 10 ** 9:
			raise Exception('Input out of range (K): {}'.format(str(K)))
		if len(S) != N:
			raise Exception('Input binary string length mismatch: {N} != {len_S}'.format(N=N, len_S=str(len(S))))
		print(str(getMaxBadness(S, K)))
except Exception as e:
	raise Exception(str(e))


for i in range(int(input())):
	(x, y) = map(int, input().split(' '))
	binarystrin = input()
	count0 = 0
	count1 = 0
	for i in binarystrin:
		if i == '1':
			count1 += 1
		elif i == '0':
			count0 += 1
	counts = [count0, count1]
	counts[0] *= -1
	final = [0]
	j = 0
	while counts[0] != 0:
		if j == len(final):
			final += [0]
		if j == y:
			j = 0
		final[j] -= 1
		counts[0] += 1
		j += 1
	j = 0
	while counts[1] != 0:
		if j == len(final):
			final += [0]
		if j == y:
			j = 0
		final[j] += 1
		counts[1] -= 1
		j += 1
	for i in range(len(final)):
		if final[i] < 0:
			final[i] *= -1
	print(max(final))


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	b = input()
	n = 0
	for i in b:
		if i == '1':
			n += 1
		else:
			n -= 1
	n = abs(n)
	if n % k != 0:
		print(n // k + 1)
	else:
		print(n // k)


for p in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(co, cz) = (0, 0)
	for i in range(n):
		if s[i] == '1':
			co += 1
		else:
			cz += 1
	res = abs(co - cz)
	res += k - 1
	print(res // k)


import math
import os
import random
import re
import sys
from math import gcd
from math import sqrt
from collections import Counter
for _ in range(int(input())):
	(a, K) = list(map(int, input().split()))
	s = input()
	z = s.count('0')
	o = s.count('1')
	x = a - z
	k = abs(x - z)
	k += (K - k % K) % K
	print(k // K)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ones = s.count('1')
	zeroes = n - ones
	if ones == zeroes:
		print(0)
	else:
		print(-(-(n - 2 * min(ones, zeroes)) // k))


def solve():
	(N, K) = map(int, input().split())
	s = input()
	O = s.count('1')
	Z = N - O
	k = abs(Z - O)
	k += (K - k % K) % K
	print(k // K)

def main():
	T = int(input())
	while T > 0:
		solve()
		T = T - 1
main()


import math

def findAns(string, k):
	c0 = string.count('0')
	c1 = string.count('1')
	remaning = abs(c0 - c1)
	if remaning > 0 and remaning <= k:
		print(1)
	else:
		print(math.ceil(remaning / k))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	findAns(string, k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	one = 0
	zero = 0
	for i in range(n):
		if s[i] == '1':
			one += 1
		else:
			zero += 1
	ans = abs(one - zero)
	if ans == 0:
		print(ans)
	elif ans <= k:
		print(1)
	else:
		print(int((ans + k - 1) / k))


import math

def solve(n1, n2, string):
	ones = string.count('1')
	zeroes = string.count('0')
	temp = abs(ones - zeroes)
	if temp == 0:
		return 0
	else:
		return math.ceil(temp / n2)
n = int(input())
results = []
for i in range(0, n):
	(n1, n2) = map(int, input().split())
	string = input()
	out = solve(n1, n2, string)
	results.append(out)
for j in results:
	print(j)


from math import ceil
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()[:N]
	list1 = [int(i) for i in S]
	(count0, count1) = (0, 0)
	for item in list1:
		if item == 1:
			count1 += 1
		else:
			count0 += 1
	z = abs(count0 - count1)
	print(ceil(z / K))


import math
import collections
for case in range(int(input())):
	(_, subseq_num) = [int(num) for num in input().split()]
	seq = [int(num) for num in input()]
	counter = collections.Counter(seq)
	frequencies = [tup[1] for tup in counter.most_common()]
	if len(frequencies) > 1:
		res = math.ceil((frequencies[0] - frequencies[1]) / subseq_num)
	else:
		res = math.ceil(frequencies[0] / subseq_num)
	print(res)


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	o = 0
	z = 0
	str1 = input()
	for i in str1:
		if i == '0':
			z = z + 1
		else:
			o = o + 1
	if z > o:
		diff = z - o
	else:
		diff = o - z
	if diff == 0:
		print(0)
	elif diff % k == 0:
		print(diff // k)
	else:
		print(diff // k + 1)


tc = int(input())
for TC in range(tc):
	(l, k) = map(int, input().split())
	s = input()
	z = s.count('0')
	o = s.count('1')
	ans = abs(z - o)
	fin = ans // k
	if ans % k != 0:
		fin += 1
	print(fin)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = input()
	n0 = l.count('0')
	n1 = l.count('1')
	r = abs(n0 - n1)
	if r == 0:
		ans = 0
	elif r <= k:
		ans = 1
	elif r % k == 0:
		ans = r // k
	else:
		ans = r // k + 1
	print(ans)


test_cases = int(input())
for i in range(test_cases):
	(total, div) = map(int, input().split(' '))
	bin_whole = input()
	count = [0, 0]
	for i in range(len(bin_whole)):
		if bin_whole[i] == '0':
			count[0] += 1
		elif bin_whole[i] == '1':
			count[1] += 1
	if abs(count[0] - count[1]) / div > int(abs(count[0] - count[1]) / div):
		print(int(abs(count[0] - count[1]) / div) + 1)
	else:
		print(int(abs(count[0] - count[1]) / div))


def solve():
	(n, k) = map(int, input().split())
	s = input()
	ones = s.count('1')
	diff = abs(n - 2 * ones)
	if not diff:
		an = 0
	elif diff % k:
		an = 1 + diff // k
	else:
		an = diff // k
	return an
tc = int(input())
for t in range(tc):
	print(solve())


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ones = s.count('1')
	diff = abs(n - 2 * ones)
	if not diff:
		an = 0
	elif diff % k:
		an = 1 + diff // k
	else:
		an = diff // k
	print(an)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	ones = input().count('1')
	diff = abs(N - 2 * ones)
	if not diff:
		an = 0
	elif diff % K:
		an = 1 + diff // K
	else:
		an = diff // K
	print(an)


ans = []
for _ in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	ones = input().count('1')
	diff = abs(N - 2 * ones)
	if not diff:
		an = 0
	elif diff % K:
		an = 1 + diff // K
	else:
		an = diff // K
	ans.append(an)
print(*ans, sep='\n')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	z = 0
	o = 0
	for j in s:
		if j == '0':
			z += 1
		else:
			o += 1
	a = min(z, o)
	z -= a
	o -= a
	r = max(z, o)
	ans = r // k
	print(ans if r % k == 0 else ans + 1)


from collections import Counter
import math
t = int(input())
for test in range(t):
	(N, K) = list(map(int, input().split(' ')))
	S = input()
	count = Counter(S)
	ones = count['1']
	zeros = count['0']
	(maximum, minimum) = (max(ones, zeros), min(zeros, ones))
	remnant = maximum - minimum
	if remnant == 0:
		print(0)
	elif remnant <= K:
		print(1)
	else:
		print(math.ceil(remnant / K))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	S = input()
	c1 = S.count('1')
	c0 = S.count('0')
	ex = abs(c1 - c0)
	if ex == 0:
		print(0)
	elif K > ex:
		print(1)
	else:
		print((ex % K != 0) + ex // K)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = s.count('0')
	b = s.count('1')
	(a, b) = (max(a, b), min(a, b))
	q = a % k
	if b < q:
		print(a // k + 1)
	elif b == q:
		print(a // k)
	else:
		print(a // k - (b - q) // k)


import sys
from math import *
from itertools import *
from bisect import bisect, bisect_left
from collections import deque, Counter, defaultdict as dd
mod = 10 ** 9 + 7

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

def ri():
	return int(input())

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

def rls():
	return list(map(str, input().split()))

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

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def lcm(x, y):
	return x * y // gcd(x, y)

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def d2b(n):
	s = bin(n).replace('0b', '')
	return (34 - len(s)) * '0' + s
for _ in range(ri()):
	(n, k) = rm()
	a = input()
	c0 = a.count('0')
	c1 = n - c0
	if c1 == c0:
		print(0)
		continue
	if c0 > c1:
		ans = (c0 - c1) // k
		if (c0 - c1) % k != 0:
			ans += 1
	else:
		ans = (c1 - c0) // k
		if (c1 - c0) % k != 0:
			ans += 1
	print(ans)


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	s = input()
	x = 0
	for i in range(n):
		if s[i] == '0':
			x += 1
		else:
			x -= 1
	x = abs(x)
	print(ceil(x / k))


import math
test_cases = int(input())
for i in range(test_cases):
	(n, k) = map(int, input().split())
	s = input()
	count_0 = s.count('0')
	count_1 = s.count('1')
	diff = abs(count_0 - count_1)
	if diff == 0:
		print(0)
	elif diff <= k:
		print(1)
	elif diff > k:
		print(math.ceil(diff / k))


import math
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input().strip()
	zeros = S.count('0')
	ones = N - zeros
	x = max(ones, zeros)
	y = min(ones, zeros)
	if x == y:
		print(0)
	elif x - y <= K:
		print(1)
	else:
		print(math.ceil((x - y) / K))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	(n0, n1) = (0, 0)
	for i in s:
		if i == '1':
			n1 += 1
		else:
			n0 += 1
	if k == 1:
		print(abs(n0 - n1))
	else:
		r = abs(n0 - n1)
		print((r + k - 1) // k)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	total_1s = sum(map(int, list(s)))
	total_0s = n - total_1s
	each_1s = total_1s // k
	left_1s = total_1s % k
	each_0s = total_0s // k
	left_0s = total_0s % k
	container = [[each_1s, each_0s] for i in range(k)]
	for i in range(left_1s):
		container[i][0] += 1
	for i in range(left_0s):
		container[i][1] += 1
	res = [abs(x - y) for (x, y) in container]
	print(max(res))


t = int(input())
for i in range(1, t + 1):
	(n, k) = map(int, input().split())
	s = input()
	zeros = 0
	ones = 0
	for i in s:
		if i == '0':
			zeros += 1
		else:
			ones += 1
	min_val = min(zeros, ones)
	zeros -= min_val
	ones -= min_val
	left = max(zeros, ones)
	res = left // k
	if left % k != 0:
		res += 1
	print(res)


import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c0 = s.count('0')
	c1 = s.count('1')
	a = c0 - c1 if c0 > c1 else c1 - c0
	b = math.ceil(a / k)
	print(b)
	t -= 1


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c0 = s.count('0')
	c1 = s.count('1')
	v = abs(c1 - c0)
	if v == 0:
		print(0)
	else:
		print(math.ceil(v / k))


import math

def ans(s, n, k):
	s = list(s)
	ones = s.count('1')
	zeros = s.count('0')
	return math.ceil(math.fabs(ones - zeros) / k)
test_cases = int(input())
while test_cases != 0:
	d = list(map(int, input().split()))
	d2 = input()
	print(ans(d2, d[0], d[1]))
	test_cases -= 1


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	(max_badness, ones_count, zeros_count) = (0, 0, 0)
	for char in s:
		if char == '1':
			ones_count += 1
		else:
			zeros_count += 1
	max_badness = abs(ones_count - zeros_count)
	for badness in range(max_badness + 1):
		if badness * k >= max_badness:
			print(badness)
			break


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	s = input()
	c = 0
	d = 0
	for i in s:
		if i == '0':
			c = c + 1
		else:
			d = d + 1
	if abs(c - d) % b == 0:
		print(abs(c - d) // b)
	else:
		print(abs(c - d) // b + 1)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	string = str(input())
	ones = 0
	for bit in string:
		if bit == '1':
			ones += 1
	zeros = n - ones
	diff = abs(ones - zeros)
	if diff % k == 0:
		print(diff // k)
	else:
		print(diff // k + 1)
	t -= 1


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	b = input()
	c0 = b.count('0')
	c1 = b.count('1')
	d = abs(c1 - c0)
	print(math.ceil(d / k))


import math
for i in range(int(input())):
	(o, z) = (0, 0)
	(a, b) = map(int, input().split())
	s = input()
	for j in s:
		if j == '1':
			o = o + 1
		else:
			z = z + 1
	d = abs(o - z)
	print(math.ceil(d / b))


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c1 = s.count('1')
	c0 = n - c1
	bd = abs(c0 - c1)
	print(math.ceil(bd / k))


for _ in range(int(input())):
	(useless, k) = map(int, input().split(' '))
	binstr = input()
	c0 = binstr.count('0')
	c1 = binstr.count('1')
	d = abs(c1 - c0)
	if d % k == 0:
		print(int(d / k))
	else:
		print(d // k + 1)


import math as mm
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	a = s.count('1')
	b = s.count('0')
	c = abs(a - b)
	if c == 0:
		print(0)
	elif k >= c:
		print(1)
	else:
		print(mm.ceil(c / k))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = str(input())
	c0 = s.count('0')
	c1 = s.count('1')
	x = abs(c0 - c1)
	(Q, rem) = divmod(x, k)
	if c0 == c1:
		print(0)
	elif x == 1:
		print(1)
	elif rem == 0:
		print(Q)
	else:
		print(Q + 1)


from math import ceil as cl
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(cl(abs(s.count('1') - s.count('0')) / k))


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	x = abs(a.count('1') - a.count('0'))
	print(int(ceil(x / k)))


import math
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	o = 0
	z = 0
	c = input()
	for j in c:
		if j == '0':
			z += 1
		else:
			o += 1
	print(math.ceil(abs(z - o) / b))