Watson gave a string $\mbox{S}$ to Sherlock. It is $N$ characters long and consists of only 1s and 0s. Now he asks:    Given an integer $\mbox{K}$, I'll pick two indices $\boldsymbol{i}$ and $j$ at random between $\mbox{1}$ and $N$, both inclusive. What's the probability that both $S[i]$ and $S[j]$ are 1 and $|i-j|\leq K$?

Input Format 

First line contains $\mathbf{T}$, the number of testcases. Each testcase consists of $N$(the length of $\mbox{S}$) and $\mbox{K}$ in one line and string in second line.     

Output Format 

Print the required probability as an irreducible fraction. If required answer is 0, output 0/1.   

Constraints 

$1\leq T\leq10^5$ 

$1\leq N\leq10^5$ 

$1\leq K\leq N$ 

$1\leq\text{Sum of N over all testcases in one file}\leq10^5$    

Sample input   

2
4 3
1011
4 1
1011

Sample output   

9/16
5/16

Explanation 

test1: Out of 16 choices, 9 pairs of $(i,j)$ satisfy our condition.  

(1,1), (1,3), (1,4), (3,1), (3,3), (3,4), (4,1), (4,3), (4,4)      

test2: Out of 16 choices, 5 pairs of $(i,j)$ satisfy our condition.   

(1,1), (3,3), (4,4), (4,3), (3,4)

Difficulty: MEDIUM_HARD
Tags: Probability

Starter code:

Solutions:
from itertools import accumulate
from fractions import gcd

def f(s, k):
	n = len(s)
	a = [0] + list(accumulate((ord(c) - ord('0') for c in s)))
	(ret, tot) = (0, n * n)
	for (i, c) in enumerate(s):
		if c == '1':
			low = max(i - k, 0)
			high = min(i + 1 + k, n)
			ret += a[high] - a[low]
	g = gcd(ret, tot)
	ret //= g
	tot //= g
	return str(ret) + '/' + str(tot)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(f(s, k))


from fractions import *
T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	S = input()
	ones = 0
	ans = 0
	for i in range(N):
		if S[i] == '1':
			ans += ones * 2 + 1
			ones += 1
		if i >= K and S[i - K] == '1':
			ones -= 1
	ans = Fraction(ans, N * N)
	print('%d/%d' % (ans.numerator, ans.denominator))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


from sys import stdin
from fractions import gcd
T = int(stdin.readline())
for _ in range(T):
	(N, K) = [int(s) for s in stdin.readline().split()]
	S = [int(s) for s in stdin.readline().strip()]
	a = 0
	ones = sum(S[1:K + 1])
	for i in range(N):
		if S[i] == 1:
			a += 1
			a += 2 * ones
		if i + K + 1 < N:
			ones += S[i + K + 1]
		if i + 1 < N:
			ones -= S[i + 1]
	g = gcd(a, N * N)
	print('%s/%s' % (a // g, N * N // g))


from fractions import gcd
testcases = int(input())
for test in range(testcases):
	(strlen, K) = (int(x) for x in str(input()).split(' '))
	S = str(input())
	curcount = sum((1 for x in S[:K] if x == '1'))
	ttotal = 0
	for (i, x) in enumerate(S[K:]):
		if x == '1':
			curcount += 1
		if S[i] == '1':
			curcount -= 1
			ttotal += 2 * curcount + 1
	for i in range(strlen - K, strlen):
		if S[i] == '1':
			curcount -= 1
			ttotal += 2 * curcount + 1
	gcdd = gcd(ttotal, strlen ** 2)
	print(str(ttotal // gcdd) + '/' + str(strlen ** 2 // gcdd))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	if k == n:
		k -= 1
	(num, ret) = (sum((x == '1' for x in a[:k + 1])), 0)
	for i in range(n):
		if a[i] == '1':
			ret += 2 * num - 1
		if a[i] == '1':
			num -= 1
		if i + k + 1 < n and a[i + k + 1] == '1':
			num += 1
	(x, y) = (ret, n * n)
	while x > 0 and y > 0:
		if x >= y:
			x %= y
		else:
			y %= x
	(num, den) = (ret // (x + y), n * n // (x + y))
	print(str(num) + '/' + str(den))


import fractions

def compute_prob(a, N, K):
	sum = 0
	poss = 0
	L = 2 * K + 1
	for i in range(-L + 1, N - K):
		if i + L - 1 < N:
			sum += a[i + L - 1]
		if i - 1 >= 0:
			sum -= a[i - 1]
		if i + K >= 0 and a[i + K]:
			poss += sum
	r = str(fractions.Fraction(poss, N ** 2))
	return r + ('/1' if r in ['1', '0'] else '')
N = int(input())
for i in range(N):
	(N, K) = map(int, input().split())
	a = [int(i) for i in input()]
	print(compute_prob(a, N, K))


def gcd(x, y):
	return gcd(y, x % y) if y else x
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	arr = input()
	(s0, s1, res, s) = (0, 0, 0, 0)
	for i in range(min(k, n)):
		if arr[i] == '1':
			s1 += 1
		else:
			s0 += 1
	for i in range(n):
		if i - k - 1 >= 0:
			if arr[i - k - 1] == '1':
				s1 -= 1
			else:
				s0 -= 1
		if i + k < n:
			if arr[i + k] == '1':
				s1 += 1
			else:
				s0 += 1
		if arr[i] == '1':
			res += s1
	g = gcd(res, n * n)
	print(res // g, n * n // g, sep='/')
	t -= 1


from fractions import Fraction
from itertools import accumulate

def solve_me(s, k):
	count = 0
	acc = list(accumulate((int(x) for x in s)))
	for (i, c) in enumerate(s):
		if c == '1':
			lower = 0 if i - k - 1 < 0 else acc[i - k - 1]
			upper = acc[-1] if i + k >= len(acc) else acc[i + k]
			count += upper - lower
	return Fraction(count, len(s) * len(s))
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = input()
	r = solve_me(s, k)
	print(r.numerator, '/', r.denominator, sep='')


def solve(K, S):
	S1 = [0]
	for s in S:
		if s == '1':
			S1.append(S1[-1] + 1)
		else:
			S1.append(S1[-1])
	c = 0
	for i in range(len(S)):
		if S[i] == '1':
			c += S1[min(i + K, len(S) - 1) + 1] - S1[max(i - K, 0)]
	return c

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b
T = int(input())
for _ in range(T):
	(N, K) = (int(_) for _ in input().split())
	S = input()
	c = solve(K, S)
	g = gcd(c, N ** 2)
	print(str(c // g) + '/' + str(N ** 2 // g))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
T = int(input())
for _ in range(T):
	[N, K] = [int(s) for s in input().split()]
	S = input()
	A = [int(S[n]) for n in range(len(S))]
	B = [A[0]]
	for i in range(1, len(A)):
		B.append(B[i - 1] + A[i])
	count = 0
	for i in range(N):
		if A[i] == 1:
			j = min(i + K, N - 1)
			count += 2 * (B[j] - B[i]) + 1
	denom = N * N
	p = gcd(count, denom)
	print(count // p, '/', denom // p, sep='')


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

def pairs(s, n, k):
	count = 0
	for i in range(n):
		if s[i] == '0':
			continue
		count += s[max(0, i - k):min(i + k + 1, n)].count('1')
	d = gcd(count, n * n)
	return (count // d, n * n // d)
T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input().rstrip()
	(a, b) = pairs(S, N, K)
	print('%d/%d' % (a, b))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


from fileinput import input
from collections import deque

def find():
	lines = input()
	noc = [int(x) for x in lines[0].strip().split()][0]
	for i in range(1, noc + 1):
		(n, k) = [int(x) for x in lines[2 * i - 1].strip().split()]
		s = [int(ele) for x in lines[2 * i].strip().split() for ele in x]
		total = n * n
		val = 0
		que = deque()
		for j in range(n):
			if s[j] == 0:
				continue
			que.append(j)
			while len(que) > 0 and abs(que[0] - j) > k:
				que.popleft()
			val += 1 + 2 * (len(que) - 1)
		(a, b) = red(val, total)
		print(str(a) + '/' + str(b), end='\n')

def red(a, b):
	if a == 0:
		return [0, 1]
	if a == 1:
		return [a, b]
	(acp, bcp) = (a, b)
	while b % a != 0:
		(a, b) = (b % a, a)
	return [acp // a, bcp // a]
find()


from fractions import gcd
s = input()
n = int(s)
for j in range(0, n):
	st = input().split(' ')
	N = int(st[0])
	K = int(st[1])
	S = input()
	d = {}
	p = 0
	a = 0
	f = 0
	l = {}
	l[0] = 0
	for i in range(len(S)):
		d[i] = int(S[i])
		f += d[i]
		l[i + 1] = f
	ret = 0
	tot = N * N
	for i in d.keys():
		if d[i] == 1:
			low = max(i - K, 0)
			high = min(i + K + 1, N)
			ret += l[high] - l[low]
	g = gcd(ret, tot)
	ret //= g
	tot //= g
	print(str(ret) + '/' + str(tot))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(length, k) = map(int, input().split())
	string = input() + '0' * k
	denominator = length * length
	numerator = sum((2 * string[i + 1:i + k + 1].count('1') + 1 for i in range(length) if string[i] == '1'))
	GCD = gcd(numerator, denominator)
	numerator //= GCD
	denominator //= GCD
	print(str(numerator) + '/' + str(denominator))


from itertools import accumulate
from fractions import gcd

def f(s, k):
	n = len(s)
	a = [0] + list(accumulate((ord(c) - ord('0') for c in s)))
	(ret, tot) = (0, n * n)
	for (i, c) in enumerate(s):
		if c == '1':
			low = max(i - k, 0)
			high = min(i + 1 + k, n)
			ret += a[high] - a[low]
	g = gcd(ret, tot)
	ret //= g
	tot //= g
	return str(ret) + '/' + str(tot)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(f(s, k))


from fractions import Fraction
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input()))
	ps = [0]
	for c in A:
		ps.append(ps[-1] + c)
	total = 0
	for i in range(1, N + 1):
		if A[i - 1] == 1:
			(lo, hi) = (max(i - K, 1), min(i + K, N))
			total += ps[hi] - ps[lo - 1]
	res = Fraction(total, N ** 2)
	print('%d/%d' % (res.numerator, res.denominator))


from fractions import Fraction

def count_ones(string, start, finish):
	return sum((string[i] == '1' for i in range(start, finish + 1)))

def prob(string, K, N):
	ans = 0
	first_one = string.find('1')
	if first_one == -1:
		return 0
	center = first_one
	left = center - K - 1 if center >= K else -1
	right = center + K if center + K < N else N - 1
	ones = count_ones(string, center, right)
	ans += ones
	for i in range(first_one + 1, N):
		center += 1
		left = center - K - 1 if center >= K else -1
		right = center + K if center + K < N else N
		if left != -1 and string[left] == '1':
			ones -= 1
		if right != N and string[right] == '1':
			ones += 1
		if string[center] == '1':
			ans += ones
	return ans
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	p = Fraction(prob(S, K, N), N ** 2)
	if p == 0:
		print('0/1')
	elif p == 1:
		print('1/1')
	else:
		print(p)


from fractions import Fraction

def valid_pairs(S, K):
	N = len(S)
	K = min(K, N - 1)
	valids = 0
	i = 0
	j = i + K
	cur_count = len([c for c in S[i:j] if c == '1'])
	valids = cur_count ** 2
	while j < N:
		if S[j] == '1':
			valids += cur_count * 2
			valids += 1
			cur_count += 1
		if S[i] == '1':
			cur_count -= 1
		i += 1
		j += 1
	return valids
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(i) for i in input().split()]
	S = input().strip()
	odds = Fraction(valid_pairs(S, K), N ** 2)
	print('%d/%d' % (odds.numerator, odds.denominator))


def gcd(a, b):
	if a == 0 or b == 0:
		return a + b
	return gcd(b, a % b)

def print_normal(a, b):
	g = gcd(a, b)
	print(str(a // g) + '/' + str(b // g))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, list(input())))
	prefix = [s[0]]
	for i in range(1, n):
		prefix.append(prefix[-1] + s[i])
	good = 0
	for i in range(n):
		if s[i]:
			good += prefix[min(n - 1, i + k)] - (0 if i == 0 else prefix[i - 1])
	print_normal(2 * good - sum(s), n * n)


from fractions import Fraction as uu

def pari(sez, k):
	zac = 0
	kon = 0
	kolk = 1
	while True:
		if kon < len(sez) - 1:
			if sez[kon + 1] - sez[zac] <= k:
				kon += 1
				kolk += (kon - zac) * 2 + 1
			else:
				zac += 1
				if kon < zac:
					kon = zac
					kolk += 1
				else:
					pass
		else:
			break
	return kolk
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().strip().split(' ')]
	sez = [i for (i, x) in enumerate(input().strip()) if x == '1']
	if len(sez) == 0:
		print('0/1')
	else:
		odg = pari(sez, k)
		if odg > 0:
			print(uu(odg, n ** 2) if odg < n ** 2 else '1/1')
		else:
			print('0/1')


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


def gcd(n, m):
	if n == 0:
		return m
	if m == 0:
		return n
	return gcd(m, n % m)

def frac(n, m):
	g = gcd(n, m)
	return str(round(n / g)) + '/' + str(round(m / g))
T = int(input())
for i in range(T):
	i1 = input().split()
	N = int(i1[0])
	K = int(i1[1])
	inp = input()
	N1 = [0]
	rightCases = 0
	for i in range(N):
		N1.append(N1[i] + int(inp[i]))
	for i in range(1, N + 1):
		if inp[i - 1] == '1':
			rightCases += (N1[min(i + K, N)] - N1[i - 1]) * 2 - 1
	totalCases = N * N
	print(frac(rightCases, totalCases))


from fractions import gcd
nTests = int(input())
for ii in range(nTests):
	(N, K) = [int(tt) for tt in input().split()]
	seq = [int(tt) for tt in input()]
	num = 0
	den = N ** 2
	ctr = 0
	for ii in range(min(K, N)):
		ctr += seq[ii]
	for ii in range(N):
		if ii + K < N:
			ctr += seq[ii + K]
		if seq[ii] == 1:
			ctr -= 1
			num += 1 + 2 * ctr
	div = gcd(num, den)
	print('{:d}/{:d}'.format(num // div, den // div))


import fractions

def prob(arr, k):
	prefix = []
	c = 0
	s = 0
	n = len(arr)
	for i in range(n):
		s += arr[i]
		prefix.append(s)
	for i in range(n):
		if arr[i] != 1:
			continue
		low = max(0, i - k)
		high = min(i + k, n - 1)
		if low == 0:
			ones = prefix[high]
		else:
			ones = prefix[high] - prefix[low - 1]
		c += ones
	g = fractions.gcd(n ** 2, c)
	return '%d/%d' % (c / g, n ** 2 / g)
cases = int(input())
for i in range(cases):
	(n, k) = input().strip().split(' ')
	n = int(n)
	k = int(k)
	s = [int(x) for x in input().strip()]
	print(prob(s, k))


import itertools
from fractions import gcd

def read_ints():
	return [int(x) for x in input().strip().split(' ')]

def read_int():
	return int(input().strip())

def read_string():
	return input().strip()
ORD_0 = ord('0')

def compute(s, k):
	n = len(s)
	a = [0] + list(itertools.accumulate((ord(c) - ORD_0 for c in s)))
	ret = 0
	tot = n * n
	for (i, c) in enumerate(s):
		if c == '1':
			(low, high) = (max(0, i - k), min(n, i + 1 + k))
			ret += a[high] - a[low]
	g = gcd(ret, tot)
	ret //= g
	tot //= g
	return str(ret) + '/' + str(tot)
T = read_int()
for _ in range(T):
	(N, K) = read_ints()
	S = read_string()
	sol = compute(S, K)
	print(sol)


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

def solve(n, k, s):
	lb = 0
	ub = 0
	total = 0
	for i in range(n):
		ub += 1 if s[i] == '1' else 0
		lb += 1 if i - k - 1 >= 0 and s[i - k - 1] == '1' else 0
		span = ub - lb
		total += (span - 1) * 2 + 1 if s[i] == '1' else 0
	num = total
	den = n * n if num > 0 else 1
	g = gcd(num, den)
	num //= g
	den //= g
	print(str(num) + '/' + str(den))
t = int(input())
for i in range(t):
	(n, k) = map(int, input().strip().split())
	s = input().strip()
	solve(n, k, s)


gcd = lambda x, y: gcd(y, x % y) if y else x

def cal_prob(i):
	(n, k) = map(int, input().split())
	(s, m) = (input().strip(), n ** 2)
	p1 = p2 = count = total = 0
	while p1 < n:
		if p2 < n:
			count += s[p2] == '1'
			p2 += 1
		if p2 - p1 > k or p2 == n:
			if s[p1] == '1':
				count -= 1
				total += 2 * count + 1
			p1 += 1
	return '{}/{}'.format(total // gcd(total, m), m // gcd(total, m))
print('\n'.join(map(cal_prob, range(int(input())))))


T = int(input())

def gcd(a, b):
	while b != 0:
		h = a % b
		a = b
		b = h
	return a

def handleTestCase():
	(N, K) = [int(x) for x in input().split()]
	bits = [int(x) for x in input()]
	(n, d) = computeProbability(K, bits)
	if n != 0:
		g = gcd(n, d)
		n //= g
		d //= g
	else:
		d = 1
	print('{}/{}'.format(n, d))

def computeProbability(K, bits):
	N = len(bits)
	windowLength = K + 1
	bitsInWindow = sum(bits[:windowLength])
	m = 0
	for i in range(N):
		left = i - K
		right = i + K
		if bits[i] == 1:
			m += bitsInWindow
		if left >= 0:
			bitsInWindow -= bits[left]
		if right + 1 < N:
			bitsInWindow += bits[right + 1]
	return (m, N * N)
for _ in range(T):
	handleTestCase()


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

def sherlock(N, K, S):
	numer = 0
	left = 0
	notdone = True
	while notdone:
		if S[left] == '1':
			SubS = S[left:min(left + K + 1, N)]
			numer += 2 * SubS.count('1') - 1
		left += 1
		if left == N:
			notdone = False
	if numer == 0:
		return '0/1'
	denom = N * N
	return str(numer // gcd(numer, denom)) + '/' + str(denom // gcd(numer, denom))
out = []
T = int(input())
for t in range(T):
	NK = input()
	(N, K) = [int(x) for x in NK.split()]
	S = input()
	out.append(sherlock(N, K, S))
for outline in out:
	print(outline)


from fractions import gcd
t = int(input().strip())
for _ in range(t):
	(N, K) = [int(x) for x in input().strip().split(' ')]
	S = [int(x) for x in list(input().strip())]
	window = 0
	for i in range(min(K + 1, N)):
		window += S[i]
	count = window if S[0] == 1 else 0
	for i in range(1, N):
		window += 1 if i + K < N and S[i + K] == 1 else 0
		window -= 1 if i - K - 1 >= 0 and S[i - K - 1] == 1 else 0
		count += window if S[i] == 1 else 0
	g = gcd(count, N * N)
	print(str(count // g) + '/' + str(N * N // g))


import re
from fractions import gcd
T = int(input())
for problem in range(T):
	(N, K) = map(int, input().split())
	S = input()
	I = [match.start() for match in re.finditer('1', S)]
	M = len(I)
	j = 1
	count = 0
	for i in range(M):
		while (j < M) & (I[min(j, M - 1)] - I[i] <= K):
			j += 1
		count += j - i
	count = 2 * count - M
	g = gcd(count, N * N)
	a = count // g
	b = N * N // g
	print(a, '/', b, sep='')


T = int(input())
from fractions import Fraction
for t in range(T):
	[N, K] = [int(i) for i in input().split(' ')]
	v = [int(i) for i in input()]
	if sum(v) == N and K + 1 >= N:
		print('1/1')
		continue
	if sum(v) == 0:
		print('0/1')
		continue
	count = 0
	currentOnes = sum(v[:K + 1])
	count += currentOnes ** 2
	for i in range(K + 1, N):
		currentOnes += v[i] - v[i - K - 1]
		if v[i] == 1:
			count += currentOnes * 2 - 1
	print(Fraction(count, N ** 2))


from fractions import Fraction

def answer_question(K, S):
	len_s = len(S)
	num_guesses = len_s ** 2
	total_successes = 0
	init_array = S[:K + 1]
	substr_trues = init_array.count('1')
	our_wins = 0
	for i_num in range(len_s):
		if S[i_num] == '1':
			our_wins += substr_trues
		(first_ind, last_ind) = [i_num - K, i_num + K + 1]
		if first_ind >= 0:
			substr_trues -= int(S[first_ind])
		if last_ind < len_s:
			substr_trues += int(S[last_ind])
	if our_wins == 0:
		print('0/1')
	elif our_wins == num_guesses:
		print('1/1')
	else:
		print(Fraction(our_wins, num_guesses))
nTimes = int(input())
for i in range(nTimes):
	[irrel, K] = map(int, [x for x in input().split()])
	S = input()
	answer_question(K, S)


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

def DoTest():
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	S = input()
	dem = N * N
	num = 0
	runningCount = S[0:K].count('1')
	for i in range(0, N):
		if i + K < N and S[i + K] == '1':
			runningCount += 1
		if S[i] == '1':
			num += runningCount
		if i >= K and S[i - K] == '1':
			runningCount -= 1
	divi = gcd(num, dem)
	print(num // divi, '/', dem // divi, sep='')
Tests = int(input())
for i in range(0, Tests):
	DoTest()


import collections
from fractions import Fraction
T = int(input())
for TT in range(T):
	(N, K) = [int(x) for x in input().split(' ')]
	S = [int(x) for x in input()]
	denominator = len(S) * len(S)
	numerator = sum([i for i in S if i])
	sums = dict()
	for i in range(N):
		sums[i] = sums.get(i - 1, 0) + S[i]
	for i in range(N):
		if not S[i]:
			continue
		numerator += sums.get(i + K, sums[N - 1]) - sums.get(i - K - 1, 0) - 1
	result = Fraction(numerator, denominator)
	print(result.numerator, '/', result.denominator, sep='')


def calcularmcd(countTot, countYes):
	if countTot == 0:
		return 1
	if countYes > 0:
		return calcularmcd(countYes, countTot % countYes)
	else:
		return countTot

def partir(s):
	inic = s.find(' ')
	return (int(s[:inic]), int(s[inic + 1:]))
t = int(input())
for n in range(t):
	almacen = []
	countYes = 0
	countTot = 0
	s = input()
	(N, K) = partir(s)
	cadena = input()
	acum = 0
	for i in range(N):
		countTot += N
		if cadena[i] is '1':
			acum += 1
		almacen.append(acum)
	for i in range(N):
		if cadena[i] is '1':
			j = i + K
			if j >= N:
				j = N - 1
			dif = almacen[j] - almacen[i]
			countYes += dif * 2 + 1
	mcd = calcularmcd(countTot, countYes)
	if mcd is 1:
		print(countYes, '/', countTot, sep='')
	else:
		print(countYes // mcd, '/', countTot // mcd, sep='')


from fractions import Fraction
for _ in range(int(input())):
	(n, k) = [int(a) for a in input().split()]
	k += 1
	s = input()
	c = s[:k].count('1')
	res = c ** 2
	for i in range(n - k):
		if s[i] == '1':
			c -= 1
		if s[i + k] == '1':
			c += 1
			res += 2 * c - 1
	if res <= 0:
		print('0/1')
	elif res >= n * n:
		print('1/1')
	else:
		print(Fraction(res, n * n))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	[n, k] = [int(x) for x in input().strip().split(' ')]
	a = [int(x) for x in list(input().strip())]
	(su, ll) = (0, 0)
	for x in range(n):
		if a[x] == 1:
			su = su + (1 + 2 * ll)
		if a[x] == 1:
			ll += 1
		if x - k >= 0 and a[x - k] == 1:
			ll -= 1
	tot = n * n
	gc = gcd(su, tot)
	print(su // gc, '/', tot // gc, sep='')


import fractions
import sys
import math
T = int(sys.stdin.readline())
for i in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	S = list(map(int, sys.stdin.readline().strip()))
	a = sum(S[:K + 1])
	b = a * (a - 1) // 2
	for i in range(1, N - K):
		a -= S[i - 1]
		if S[i + K] == 1:
			b += a
			a += 1
	suM_ = sum(S) + 2 * b
	m = N ** 2
	gcd = fractions.gcd(suM_, m)
	print('%d/%d' % (suM_ // gcd, m // gcd))


def to_int_list(s):
	return list(map(int, s.split(' ')))
from fractions import gcd

class Node:

	def __init__(self, pos, next):
		self.next = next
		self.pos = pos

def compute(n, k, s: str):
	cnt = 0
	q_len = 0
	first = None
	last = None
	for i in range(len(s)):
		if s[i] == '1':
			if first is None:
				first = last = Node(i, next=None)
			else:
				last.next = Node(i, next=None)
				last = last.next
				node = first
				while i - node.pos > k:
					q_len -= 1
					node = node.next
				first = node
			cnt += 2 * q_len + 1
			q_len += 1
	d = 1 if cnt == 0 else gcd(cnt, n * n)
	return '0/1' if cnt == 0 else '{}/{}'.format(cnt // d, n * n // d)
T = int(input())
for i in range(T):
	nk = to_int_list(input())
	(n, k) = (nk[0], nk[1])
	s = input()
	print(compute(n, k, s))


import fractions
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	c = [ch == '1' for ch in s]
	for i in range(1, n):
		c[i] += c[i - 1]
	val = 0
	for i in range(n):
		if s[i] == '0':
			continue
		val += c[min(n - 1, i + k)]
		if i > k:
			val -= c[i - k - 1]
	den = n * n
	g = fractions.gcd(val, den)
	val //= g
	den //= g
	print(str(val) + '/' + str(den))


import fractions
import sys
t = int(next(sys.stdin))
for _ in range(t):
	(n, k) = map(int, next(sys.stdin).split())
	s = next(sys.stdin).strip()
	s_ = [0]
	for c in s:
		s_.append(s_[-1] + int(c))
	good_cnt = 0
	for i in range(n):
		if int(s[i]):
			good_cnt += s_[min(n, i + 1 + k)] - s_[max(0, i - k)]
	ans = fractions.Fraction(good_cnt, n ** 2)
	print('{}/{}'.format(ans.numerator, ans.denominator))


from fractions import Fraction
T = int(input())
for i in range(T):
	(N, K) = input().split(' ')
	N = int(N)
	K = int(K)
	S = input()
	g = 0
	c = S.count('1', 0, K)
	for j in range(N):
		if j + K <= N - 1:
			c += int(S[j + K] == '1')
		if j - K - 1 >= 0:
			c -= int(S[j - K - 1] == '1')
		if S[j] == '1':
			g += c
	if N * N > g > 0:
		print(Fraction(g, N * N))
	elif g > 0:
		print('1/1')
	else:
		print('0/1')


def gcd(a, b):
	if a == b or b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input().strip())
for _ in range(t):
	(n, k) = [int(x.strip()) for x in input().split()]
	s = [int(x) for x in list(input().strip())]
	runTot = 0
	count = 0
	numOnes = 0
	for i in range(min(k + 1, n)):
		if s[i] == 1:
			runTot += 1
			numOnes += 1
	count = runTot * (runTot - 1) // 2
	for i in range(k + 1, n):
		runTot -= s[i - k - 1]
		if s[i] == 1:
			count += runTot
			runTot += 1
			numOnes += 1
	count = count * 2
	count += numOnes
	g = gcd(n * n, count)
	print(str(count // g) + '/' + str(n * n // g))


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

def prob(arr, k, n):
	ctr = 0
	ones = 0
	joke = sum(arr[:min(k, n)])
	for i in range(n):
		if i != 0:
			joke = joke - arr[i - 1]
		if i < n - k:
			joke += arr[i + k]
		if arr[i] == 1:
			ones += 1
			ctr += joke
	return (ctr, ones)
for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	arr = [int(x) for x in input()]
	(numer, ones) = prob(arr, k, n)
	numer = numer * 2 - ones
	denom = n * n
	nice = hcf(numer, denom)
	numer = numer // nice
	denom = denom // nice
	st = str(numer) + '/' + str(denom)
	print(st)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
T = int(input())
for cntT in range(T):
	(N, K) = [int(x) for x in input().split()]
	string = input()
	a = [i for (i, n) in enumerate(string) if int(n) == 1]
	s = 0
	for i in a:
		s += string[max(0, i - K):min(N, i + K + 1)].count('1')
	g = gcd(s, N * N)
	print('{}/{}'.format(s // g, N * N // g))


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b != 0:
		temp = a % b
		a = b
		b = temp
	return a

def gcd_Stein(a, b):
	if a < b:
		(a, b) = (b, a)
	if 0 == b:
		return a
	if a % 2 == 0 and b % 2 == 0:
		return 2 * gcd_Stein(a / 2, b / 2)
	if a % 2 == 0:
		return gcd_Stein(a / 2, b)
	if b % 2 == 0:
		return gcd_Stein(a, b / 2)
	return gcd_Stein((a + b) / 2, (a - b) / 2)
t = int(input())
for i in range(t):
	(n, k) = [int(a) for a in input().split()]
	s = [int(a) for a in list(input())]
	s_sum = 0
	c = sum(s[0:k])
	for (ii, bi) in enumerate(s):
		if ii + k <= n - 1:
			c += s[ii + k]
		if ii - k - 1 >= 0:
			c -= s[ii - k - 1]
		if bi == 1:
			s_sum += c
	nn = n * n
	g = gcd_Stein(nn, s_sum)
	print('%d/%d' % (s_sum // g, nn // g))


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input()]
	s = sum(arr[0:k + 1])
	left = -k
	right = k
	mid = 0
	x = s if arr[0] == 1 else 0
	for i in range(1, n):
		if left >= 0:
			s -= arr[left]
		if right < n - 1:
			s += arr[right + 1]
		if arr[i] == 1:
			x += s
		left += 1
		right += 1
	y = n * n
	g = gcd(x, y)
	x //= g
	y //= g
	if x == 0:
		print('0/1')
	else:
		print('%d/%d' % (x, y))


import sys
from fractions import Fraction
T = int(sys.stdin.readline().strip())

def computeProb(st, k):
	l = len(st)
	oneCount = 0
	count = 0
	for i in range(l):
		if st[i] == '1':
			count += oneCount
			oneCount += 1
		if i >= k and st[i - k] == '1':
			oneCount -= 1
	count *= 2
	count += sum([int(x) for x in st])
	return (count, l * l)
for i in range(T):
	(N, k) = [int(x) for x in sys.stdin.readline().strip().split()]
	st = sys.stdin.readline().strip()
	(nom, den) = computeProb(st, k)
	if nom == den:
		print('1/1')
	elif nom == 0:
		print('0/1')
	else:
		print(Fraction(nom, den))


from fractions import Fraction
T = int(input().strip())
for _ in range(T):
	(N, K) = list(map(int, input().strip().split()))
	S = input().strip()
	E = 0
	num1 = 0
	inwindow = 0
	for i in range(min(N, K + 1)):
		if S[i] == '1':
			inwindow += 1
	j = K
	for i in range(len(S)):
		if S[i] == '1':
			num1 += 1
			E += inwindow
			inwindow -= 1
		if j < len(S) - 1:
			j += 1
			if S[j] == '1':
				inwindow += 1
	num = 2 * E - num1
	if num == 0:
		print('0/1')
	else:
		P = Fraction(num, N ** 2)
		print(str(P.numerator) + '/' + str(P.denominator))


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

def n_pairs(n_ones):
	return 1 + (n_ones - 1) * 2
debug = 0

def count(n, k, s):
	num = 0
	i = 0
	while i < n and s[i] != '1':
		i += 1
	if i == n:
		return (0, 1)
	n_ones = 1
	j = i
	while j < min(n - 1, i + k):
		j += 1
		if s[j] == '1':
			n_ones += 1
	if debug:
		print('First window', s[i:i + k + 1], n_ones)
	num += n_pairs(n_ones)
	while True:
		j = i + 1
		while j < n and s[j] != '1':
			j += 1
		if j == n:
			break
		n_ones -= 1
		for ii in range(i + k + 1, min(n, j + k + 1)):
			if s[ii] == '1':
				n_ones += 1
		if debug:
			print('Window', s[j:j + k + 1], n_ones)
		num += n_pairs(n_ones)
		i = j
	denom = n * n
	return (num, denom)

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		s = input()
		(num, denom) = count(n, k, s)
		g = gcd(num, denom)
		print('{}/{}'.format(num // g, denom // g))
main()


from fractions import Fraction, gcd
for _ in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	s = input()
	count = []
	result = s.count('1')
	first_one = s.find('1')
	pairs = s[first_one + 1:first_one + K + 1].count('1')
	result += 2 * pairs
	for x in range(first_one + 1, len(s) - 1):
		if s[x] == '1':
			pairs = s[x + 1:x + K + 1].count('1')
			result += 2 * pairs
	g = gcd(result, len(s) ** 2)
	print('{}/{}'.format(result // g, len(s) ** 2 // g))


t = int(input())

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for __ in range(0, t):
	(n, k) = map(int, input().split())
	s = str(input())
	a = n * n
	count = 0
	pr = [0 for __ in range(0, n)]
	for i in range(0, n):
		pr[i] = pr[i - 1]
		if s[i] == '1':
			if i:
				if i > k:
					count += pr[i] - pr[i - k - 1] << 1
				else:
					count += pr[i] << 1
			pr[i] += 1
			count += 1
	g = gcd(a, count)
	print('%d/%d' % (count // g, a // g))


from fractions import Fraction

def process_string(str_length, string, band):
	true_count = 0
	for i in range(str_length):
		if string[i].count('1'):
			if i < band:
				true_count += string[:i + band + 1].count('1')
			else:
				true_count += string[i - band:i + band + 1].count('1')
	return Fraction(true_count, str_length ** 2)
test_cases = int(input())
for _ in range(test_cases):
	(N, k) = [int(i) for i in input().split(' ')]
	S = input()
	p = process_string(N, S, k)
	if p == 1:
		print('1/1')
	elif p == 0:
		print('0/1')
	else:
		print(p)


from fractions import Fraction
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	num = 0
	mult = []
	cur = 0
	for i in range(n + k + 1):
		if i < n and s[i] == '1':
			cur += 1
		if i - k - 1 >= 0 and s[i - k - 1] == '1':
			cur -= 1
		mult.append(cur)
	for (i, c) in enumerate(s):
		if c == '1':
			num += 2 * mult[i + k] - 1
	if num == 0:
		print('0/1')
	elif num == n * n:
		print('1/1')
	else:
		print(Fraction(num, n * n))


import fractions, sys
T = int(input())
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	S = list(map(int, input().strip()))
	x = sum(S[:K + 1])
	pairs = x * (x - 1) // 2
	for i in range(1, N - K):
		x -= S[i - 1]
		if S[i + K] == 1:
			pairs += x
			x += 1
	valid = sum(S) + 2 * pairs
	total = N ** 2
	gcd = fractions.gcd(valid, total)
	print('%d/%d' % (valid // gcd, total // gcd))


def testcase():
	(n, k) = [int(a) for a in input().split(' ')]
	data = input()
	ones_sum = [0] * n
	for i in range(n):
		ones_sum[i] = 0 if i == 0 else ones_sum[i - 1]
		ones_sum[i] += 1 if data[i] == '1' else 0
	result = ones_sum[n - 1]
	for i in range(1, n):
		if data[i] == '1':
			end = i - 1
			begin = max(0, i - k)
			result += ones_sum[end] * 2
			if begin > 0:
				result -= ones_sum[begin - 1] * 2

	def find_gcd(a, b):
		return a if b == 0 else find_gcd(b, a % b)
	all = n * n
	if result == 0:
		print('0/1')
	else:
		gcd = find_gcd(result, all)
		print('{}/{}'.format(result // gcd, all // gcd))
t = int(input())
for i in range(t):
	testcase()


import fractions
T = int(input())
for _ in range(T):
	[N, K] = [int(x) for x in input().split(' ')]
	S = input()
	counter = S[0:K + 1].count('1')
	num1 = 0
	for i in range(N):
		if S[i] == '1':
			num1 += counter
		a = i + 1 - K
		b = i + 1 + K
		if a > 0:
			counter -= int(S[a - 1])
		if b < N:
			counter += int(S[b])
	res = fractions.Fraction(num1, N * N)
	print('%d/%d' % (res.numerator, res.denominator))


from fractions import Fraction
T = int(input())
for i in range(T):
	(N, K) = input().split(' ')
	N = int(N)
	K = int(K)
	S = input()
	g = 0
	c = S.count('1', 0, K)
	for j in range(N):
		if j + K <= N - 1:
			c += int(S[j + K] == '1')
		if j - K - 1 >= 0:
			c -= int(S[j - K - 1] == '1')
		if S[j] == '1':
			g += c
	if N * N > g > 0:
		print(Fraction(g, N * N))
	elif g > 0:
		print('1/1')
	else:
		print('0/1')


from queue import Queue
from math import gcd
t = int(input())
for test in range(t):
	(n, k) = [int(i) for i in input().split()]
	zando = [idx for (idx, i) in enumerate(input()) if i == '1']
	count = 0
	q = Queue()
	q_list_idx = 0
	for number in zando:
		if not q.empty():
			while number - zando[q_list_idx] > k:
				m = q.get()
				count += q.qsize()
				q_list_idx += 1
		q.put(number)
		count += q.qsize()
	while not q.empty():
		q.get()
		count += q.qsize()
	total_possibilities = n ** 2
	gc = gcd(count, total_possibilities)
	print('{}/{}'.format(int(count / gc), int(total_possibilities / gc)))


from fractions import Fraction
T = int(input())
for i in range(T):
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	S = input()
	g = 0
	c = S.count('1', 0, K)
	for j in range(N):
		if j + K <= N - 1:
			c += int(S[j + K] == '1')
		if j - K - 1 >= 0:
			c -= int(S[j - K - 1] == '1')
		if S[j] == '1':
			g += c
	if N * N > g > 0:
		print(Fraction(g, N * N))
	elif g > 0:
		print('1/1')
	else:
		print('0/1')


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

def probability(s, n, k):
	p = 0
	r = 0
	for i in range(n):
		if s[i]:
			p += r
			r += 1
		if i >= k and s[i - k]:
			r -= 1
	p *= 2
	p += sum(s)
	if p == 0:
		return '0/1'
	q = n ** 2
	d = gcd(p, q)
	return '{}/{}'.format(p // d, q // d)
T = int(input())
for _ in range(T):
	(n, k) = (int(x) for x in input().strip().split(' '))
	s = [int(c) for c in input().strip()]
	print(probability(s, n, k))


from fractions import Fraction

def num_valid_pairs(arr, k):
	total = 0
	window = 0
	for i in range(len(arr)):
		if arr[i]:
			total += window
			window += 1
		if i >= k and arr[i - k]:
			window -= 1
	total *= 2
	total += sum(arr)
	return total

def print_fraction(arr, k):
	num = num_valid_pairs(arr, k)
	den = len(arr) ** 2
	if num == den:
		print('1/1')
	elif num:
		print(Fraction(num, den))
	else:
		print('0/1')
import sys
T = int(sys.stdin.readline())
for i in range(T):
	(N, K) = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().strip()))
	print_fraction(arr, K)


import sys
from fractions import Fraction

def good_cases(n, k, s):
	good = 0
	window_count = s.count('1', 0, k)
	for i in range(n):
		if i + k <= n - 1:
			window_count += int(s[i + k])
		if i - k > 0:
			window_count -= int(s[i - k - 1])
		if s[i] == '1':
			good += window_count
	return good

def print_outcome(n, k, s):
	nom = good_cases(n, k, s)
	denom = n * n
	if nom == denom:
		print('1/1')
	elif nom:
		print(Fraction(nom, denom))
	else:
		print('0/1')
n_cases = int(sys.stdin.readline())
for i in range(n_cases):
	(n, k) = (int(x) for x in sys.stdin.readline().split())
	s = sys.stdin.readline().strip()
	print_outcome(n, k, s)


from fractions import Fraction

def find_prob(N, K, str_):
	total = 0
	window = 0
	for (i, s) in enumerate(str_):
		if s == '1':
			total += window
			window += 1
		if i >= K and str_[i - K] == '1':
			window -= 1
	total *= 2
	total += sum([int(i) for i in str_])
	frac = Fraction(total, N * N)
	if frac == 0:
		print('0/1')
	elif frac == 1:
		print('1/1')
	else:
		print(frac)
num_cases = int(input())
for _ in range(num_cases):
	(N, K) = [int(i) for i in input().split(' ')]
	str_ = input()
	find_prob(N, K, str_)


import sys, fractions

def getProb(n, k, binary):
	finalsum = 0
	windowsum = 0
	for i in range(min(k + 1, n)):
		windowsum += int(binary[i])
	for i in range(n):
		if binary[i] == '1':
			finalsum += windowsum
		if i + k + 1 < n:
			windowsum += int(binary[i + k + 1])
		if i - k >= 0:
			windowsum -= int(binary[i - k])
	return finalsum
total = int(sys.stdin.readline().strip())
for i in range(total):
	[n, k] = sys.stdin.readline().split()
	n = int(n)
	k = int(k)
	binary = sys.stdin.readline().strip()
	num = getProb(n, k, binary)
	denom = n ** 2
	if num == 0:
		print('0/1')
	elif num == denom:
		print('1/1')
	else:
		print(fractions.Fraction(num, denom))


import sys
from fractions import Fraction

def count(S, K, N):
	g = 0
	c = S.count('1', 0, K)
	for j in range(N):
		if j + K <= N - 1:
			c += int(S[j + K] == '1')
		if j - K - 1 >= 0:
			c -= int(S[j - K - 1] == '1')
		if S[j] == '1':
			g += c
	return g

def formatanswer(n, d):
	if d > n > 0:
		print(Fraction(n, d))
	elif n > 0:
		print('1/1')
	else:
		print('0/1')
nbTests = int(input())
for i in range(nbTests):
	(N, K) = input().split(' ')
	N = int(N)
	K = int(K)
	S = input()
	formatanswer(count(S, K, N), N * N)


from fractions import Fraction
T = int(input())
for i in range(T):
	(N, K) = input().split(' ')
	N = int(N)
	K = int(K)
	S = input()
	g = 0
	c = S.count('1', 0, K)
	for j in range(N):
		if j + K <= N - 1:
			c += int(S[j + K] == '1')
		if j - K - 1 >= 0:
			c -= int(S[j - K - 1] == '1')
		if S[j] == '1':
			g += c
	if N * N > g > 0:
		print(Fraction(g, N * N))
	elif g > 0:
		print('1/1')
	else:
		print('0/1')


T = int(input())
from math import gcd
for t0 in range(T):
	(N, K) = (int(a) for a in input().split())
	A = list(input())
	A = [int(a) for a in A]
	B = []
	s = 0
	tot = 0
	if N == K:
		K -= 1
	for i in range(K + 1):
		if A[i] == 1:
			tot += 1 + 2 * s
			s += 1
		B.append(A[i])
	for i in range(K + 1, N):
		if B[0] == 1:
			s -= 1
		B = B[1:]
		if A[i] == 1:
			tot += 1 + 2 * s
			s += 1
		B.append(A[i])
	M = N ** 2
	g = gcd(tot, M)
	tot //= g
	M //= g
	print('{}/{}'.format(tot, M))


def gcd(a, b):
	while b != 0:
		temp = b
		b = a % b
		a = temp
	return a
cases = int(input())
for i in range(0, cases):
	(N, K) = map(int, input().split())
	S = input()
	numer = N * (2 * K + 1) - K * (K + 1)
	count = [0] * N
	zeros = []
	for j in range(0, N):
		if S[j] == '0':
			zeros.append(j)
			numer -= 2 * (min(K + j + 1, N) - max(j + 1 - K, 1)) + 1
			for k in range(max(0, len(zeros) - K - 1), len(zeros)):
				if zeros[k] >= j - K:
					numer += 2 * (len(zeros) - 1 - k)
					break
	g = gcd(numer, N * N)
	print(str(numer // g) + '/' + str(N * N // g))


from fractions import Fraction as f
t = int(input())
for ti in range(t):
	(n, k) = [int(s) for s in input().split()]
	s = input()
	c = s.count('1', 0, k)
	c1 = c * c
	for i in range(k, n):
		if s[i] == '1':
			c1 += 2 * c + 1
			c += 1
		if s[i - k] == '1':
			c -= 1
	p = f(c1, n ** 2)
	print(str(p.numerator) + '/' + str(p.denominator))


def gcd(x, y):
	a = max(x, y)
	b = min(x, y)
	while b > 0:
		(a, b) = (b, a % b)
	return a

def compute_prob(x, k):
	n = len(x)
	num = [0] * n
	den = [1] * n
	num[0] = x[0]
	y = x[0]
	for t in range(1, n):
		if t > k:
			y -= x[t - k - 1]
		num[t] = num[t - 1] * t ** 2 + den[t - 1] * (2 * y + 1) * x[t]
		den[t] = den[t - 1] * (t + 1) ** 2
		d = gcd(num[t], den[t])
		num[t] //= d
		den[t] //= d
		y += x[t]
	return (num[n - 1], den[n - 1])
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	x = [int(e) for e in input().strip()]
	(a, b) = compute_prob(x, k)
	print('{}/{}'.format(a, b))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	a = s.count('1')
	if a == 0:
		print('0/1')
	elif a == 1:
		print('1/{}'.format(n ** 2))
	else:
		res = 0
		fs = len(s)
		s = (k + 1) * '0' + s + (k + 1) * '0'
		ql = 0
		i = s.index('1')
		il = i - k
		ir = i + k
		qr = s[i + 1:ir + 1].count('1') + 1
		while ir < len(s) - 1:
			if s[i] == '1':
				res += ql + qr
				ql += 1
				qr -= 1
			if s[il] == '1':
				ql -= 1
			if s[ir + 1] == '1':
				qr += 1
			i += 1
			il += 1
			ir += 1
		gcd = lambda a, b: gcd(b, a % b) if b else a
		z = n ** 2
		c = gcd(res, z)
		res //= c
		z //= c
		print('{}/{}'.format(res, z))


from fractions import Fraction as F
nCases = int(input())
for x in range(nCases):
	(siz, k) = map(int, input().split())
	strL = input()
	a = -1
	icc = 0
	for n in strL:
		a += 1
		if n == '1':
			icc += strL.count('1', a, a + k + 1) * 2 - 1
	if icc == 0:
		print('0/1')
	elif icc == siz ** 2:
		print('1/1')
	else:
		print(F(icc, siz ** 2))


def gdm(a, b):
	while a % b:
		(a, b) = (b, a % b)
	return b
t = int(input())
for ti in range(t):
	(n, k) = input().split()
	(n, k) = [int(n), int(k)]
	s = input()
	enum = 0
	for i in range(n):
		if s[i] == '1':
			enum += 1 + 2 * s[min(i + 1, n):min(i + k + 1, n)].count('1')
	if enum:
		gd = gdm(enum, n ** 2)
		print('%d/%d' % (enum / gd, n ** 2 / gd))
	else:
		print('0/1')


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	counter = [0]
	for v in S:
		counter.append(counter[-1] + 1 if v == '1' else counter[-1])
	Pn = sum(map(lambda i: 0 if S[i] == '0' else counter[min(N, i + K + 1)] - counter[max(0, i - K)], range(N)))
	P = Fraction(Pn, N ** 2)
	print('{}/{}'.format(P.numerator, P.denominator))


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	counter = [0]
	for v in S:
		counter.append(counter[-1] + 1 if v == '1' else counter[-1])
	Pn = sum(map(lambda i: 0 if S[i] == '0' else counter[min(N, i + K + 1)] - counter[max(0, i - K)], range(N)))
	P = Fraction(Pn, N ** 2)
	print('{}/{}'.format(P.numerator, P.denominator))


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	counter = [0]
	for v in S:
		counter.append(counter[-1] + 1 if v == '1' else counter[-1])
	Pn = sum(map(lambda i: 0 if S[i] == '0' else counter[min(N, i + K + 1)] - counter[max(0, i - K)], range(N)))
	P = Fraction(Pn, N ** 2)
	print('{}/{}'.format(P.numerator, P.denominator))


from fractions import Fraction
t = int(input(''))
for t1 in range(t):
	(n, k) = input('').split(' ')
	(n, k) = (int(n), int(k))
	s = list(map(int, list(input(''))))
	d = []
	temp = 0
	for i in s:
		if i == 0:
			d.append(0)
		if i == 1:
			temp += 1
			d.append(temp)
	count = 0
	for i in range(len(s)):
		if s[i] == 1:
			count += 1
			if i + k < len(s):
				t1 = i + k
			else:
				t1 = len(s) - 1
			while s[t1] != 1:
				t1 -= 1
			count += 2 * (d[t1] - d[i])
	if count != 0 and count != n ** 2:
		print(Fraction(count, n ** 2))
	elif count == n ** 2:
		print('1/1')
	else:
		print('0/1')


from fractions import Fraction

def count_cases(n, k, s):
	n_ones_in_window = 0
	n_cases = 0
	for i in range(n):
		if s[i]:
			n_cases += n_ones_in_window
			n_ones_in_window += 1
		if i >= k and s[i - k]:
			n_ones_in_window -= 1
	n_cases *= 2
	n_cases += sum(s)
	return n_cases
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = [int(x) for x in input()]
	n_cases = count_cases(n, k, s)
	f = Fraction(n_cases, n ** 2)
	if f.denominator == 1:
		print('{}/1'.format(f))
	else:
		print('{}'.format(f))


from fractions import Fraction

def sherlock(N, K, S):
	if N == 1:
		denom = 1
	else:
		denom = N * N
	count = 0
	i = 0
	for i in range(N):
		if S[i] == '1':
			count += 1
			count += 2 * S[i + 1:i + K + 1].count('1')
	a = Fraction(count, denom)
	if a == 0:
		return '0/1'
	elif a == 1:
		return '1/1'
	else:
		return a
n = int(input())
for x in range(n):
	(N, K) = input().split()
	S = input().strip()
	print(sherlock(int(N), int(K), S))


s = '1011'
K = 4
N = len(s)
import sys
from fractions import gcd

def find_combos(s, K, N):
	s_window = s[0:K]
	count_ones = s_window.count('1')
	result = count_ones * count_ones
	for i in range(0, N - K):
		first_ch = s[i]
		last_ch = s[i + K]
		count_ones -= int(first_ch)
		if last_ch == '1':
			result += count_ones * 2 + 1
			count_ones += 1
	div = gcd(result, N * N)
	if result == 0:
		print('0/1')
		return
	print('%d/%d' % (result // div, N * N // div))
_ = sys.stdin.readlines()
lines = [word.split() for word in _[1:]]
for ix in range(0, len(lines) // 2):
	N = int(lines[ix * 2][0])
	K = int(lines[ix * 2][1]) + 1
	s = lines[ix * 2 + 1][0]
	find_combos(s, K, N)


from fractions import Fraction

def sherlock(N, K, S):
	denom = N * N
	count = 0
	i = 0
	for i in range(N):
		if S[i] == '1':
			count += 1
			count += 2 * S[i + 1:i + K + 1].count('1')
	a = Fraction(count, denom)
	if a == 0:
		return '0/1'
	elif a == 1:
		return '1/1'
	else:
		return a
n = int(input())
for x in range(n):
	(N, K) = input().split()
	S = input().strip()
	print(sherlock(int(N), int(K), S))


import sys
import math
from fractions import Fraction
n = int(input().strip())
for s in range(n):
	arg = input().strip().split(' ')
	l = int(arg[0])
	k = int(arg[1])
	list = input()
	count = 0
	ones = 0
	first = 0
	i1 = k
	i0 = 0
	if l - k <= 1:
		for j in range(l):
			if list[j] == '1':
				ones += 1
		if ones == 0:
			print('0/1')
		elif ones == l:
			print('1/1')
		else:
			print(Fraction(pow(ones, 2), pow(l, 2)))
		continue
	for j in range(k + 1):
		if list[j] == '1':
			ones += 1
	stop = k + 1
	if l - k - 1 < stop:
		stop = l - k - 1
	for i in range(stop):
		if list[i] == '1':
			count += ones
		i1 += 1
		if list[i1] == '1':
			ones += 1
	for i in range(stop, l - k - 1):
		if list[i0] == '1':
			ones -= 1
		i0 += 1
		if list[i] == '1':
			count += ones
		i1 += 1
		if list[i1] == '1':
			ones += 1
	if stop == l - k - 1:
		for i in range(stop, k + 1):
			if list[i] == '1':
				count += ones
		for i in range(k + 1, l):
			if list[i0] == '1':
				ones -= 1
			i0 += 1
			if list[i] == '1':
				count += ones
	else:
		for i in range(l - k - 1, l):
			if list[i0] == '1':
				ones -= 1
			i0 += 1
			if list[i] == '1':
				count += ones
	if count == 0:
		print('0/1')
	else:
		print(Fraction(count, pow(l, 2)))


from fractions import gcd
T = int(input())
for _ in range(T):
	[N, K] = input().split()
	[N, K] = [int(N), int(K)]
	S = input()
	s = '0' * K + S + '0' * K
	sum0 = 0
	for i in range(2 * K + 1):
		sum0 += int(s[i])
	if s[K] == '1':
		numn = sum0
	else:
		numn = 0
	for i in range(1, N):
		sum0 = sum0 - int(s[i - 1]) + int(s[i + 2 * K])
		if s[i + K] == '1':
			numn += sum0
	numd = N * N
	g = gcd(numn, numd)
	print('%d/%d' % (numn // g, numd // g))


import fractions

def solve(bits, k):
	choices = 0
	ones = 0
	for (i, bit) in enumerate(bits):
		if i - (k + 1) >= 0:
			ones -= bits[i - (k + 1)]
		if bit == 1:
			choices += ones * 2
		ones += bit
	top = choices + bits.count(1)
	bottom = len(bits) * len(bits)
	prob = fractions.Fraction(top, bottom)
	return '%d/%d' % (prob.numerator, prob.denominator)
tests = int(input())
for test in range(tests):
	(n, k) = map(int, input().split())
	bits = [int(x) for x in input()]
	print(solve(bits, k))


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	counter = [0]
	for v in S:
		counter.append(counter[-1] + 1 if v == '1' else counter[-1])
	Pn = sum(map(lambda i: 0 if S[i] == '0' else counter[min(N, i + K + 1)] - counter[max(0, i - K)], range(N)))
	P = Fraction(Pn, N ** 2)
	print('{}/{}'.format(P.numerator, P.denominator))


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	counter = [0]
	for v in S:
		counter.append(counter[-1] + 1 if v == '1' else counter[-1])
	Pn = sum(map(lambda i: 0 if S[i] == '0' else counter[min(N, i + K + 1)] - counter[max(0, i - K)], range(N)))
	P = Fraction(Pn, N ** 2)
	print('{}/{}'.format(P.numerator, P.denominator))


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	g = 0
	c = S.count('1', 0, K)
	for j in range(N):
		if j + K <= N - 1:
			c += int(S[j + K] == '1')
		if j - K - 1 >= 0:
			c -= int(S[j - K - 1] == '1')
		if S[j] == '1':
			g += c
	f = Fraction(g, N ** 2)
	print('{}/{}'.format(f.numerator, f.denominator))


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	counter = [0]
	for v in S:
		counter.append(counter[-1] + 1 if v == '1' else counter[-1])
	Pn = sum(map(lambda i: 0 if S[i] == '0' else counter[min(N, i + K + 1)] - counter[max(0, i - K)], range(N)))
	P = Fraction(Pn, N ** 2)
	print('{}/{}'.format(P.numerator, P.denominator))


from fractions import gcd

def main():
	T = int(input())
	for _ in range(T):
		(N, K) = map(int, input().split())
		S = input()
		C = c1 = j = 0
		for i in range(N):
			while j < N and j - i <= K:
				if S[j] == '1':
					c1 += 1
				j += 1
			if S[i] == '1':
				c1 -= 1
				C += 1 + 2 * c1
		D = N * N
		g = gcd(C, D)
		print('%d/%d' % (C // g, D // g))
main()


import itertools as itt
from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	s = input()
	accum = list(itt.accumulate(map(int, list(s))))
	accum.insert(0, 0)
	num = 0
	for i in range(1, len(s) + 1):
		if s[i - 1] == '1':
			num += accum[min(N, i + K)] - accum[max(0, i - K - 1)]
	prob = Fraction(num, N ** 2)
	print('{}/{}'.format(prob.numerator, prob.denominator))


from fractions import Fraction
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	counter = [0]
	for v in S:
		counter.append(counter[-1] + 1 if v == '1' else counter[-1])
	Pn = sum(map(lambda i: 0 if S[i] == '0' else counter[min(N, i + K + 1)] - counter[max(0, i - K)], range(N)))
	P = Fraction(Pn, N ** 2)
	print('{}/{}'.format(P.numerator, P.denominator))