Chef has binary string A of length N. He constructs a new binary string B by concatenating M copies of A together. For example, if A = \texttt{"10010"}, M = 3, then B = \texttt{"100101001010010"}.

Chef calls an index i (1 ≤ i ≤ N \cdot M) *good* if:
pref_{i} = suf_{i + 1}.

Here, pref_{j} = B_{1} + B_{2} + \ldots + B_{j} and
suf_{j} = B_{j} + B_{j + 1} + \ldots + B_{N \cdot M} (Note that suf_{N \cdot M + 1} = 0 by definition) 

Chef wants to find the number of good indices in B. Can you help him do so?

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains two space-separated integers N and M — the length of the binary string A and the number of times A is concatenated to form 
- The second line of each test case contains a binary string A of length N containing 0s and 1s only.

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

For each test case, output the number of good indices in B.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 10^{5}$
$A$ is a binary string, i.e, contains only the characters $0$ and $1$.
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.
- The sum of $M$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2 2
00
2 4
11
3 3
101

----- Sample Output 1 ------ 
4
1
2

----- explanation 1 ------ 
Test case $1$: $B = \texttt{"0000"}$. In this string, all the indices are good.

Test case $2$: $B = \texttt{"11111111"}$. In this string, only $i = 4$ is good.

Test case $3$: $B = \texttt{"101101101"}$. In this string, $i = 4$ and $i = 5$ are good.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Range queries

Complete search

Mathematics

Data structures
Skill types: Sorting

Data structures

Range queries

Complete search

Starter code:

Solutions:
import math
T = int(input())
for i in range(T):
	(N, M) = [int(z) for z in input().strip().split()]
	A = [int(z) for z in input()]
	summer = sum(A)
	if summer == 0:
		print(N * M)
	else:
		tot_sum = summer * M
		if tot_sum % 2 == 1:
			print(0)
		elif M % 2 == 1:
			counter = 0
			temp_sum = 0
			for i in range(N):
				temp_sum += A[i]
				if temp_sum == summer / 2:
					counter += 1
			print(counter)
		else:
			arr1 = A + A
			counter = 0
			temp_sum = 0
			for i in range(2 * N):
				temp_sum += arr1[i]
				if temp_sum == summer:
					counter += 1
			print(counter)


for _ in range(int(input())):
	(n, m) = (int(i) for i in input().split())
	a = input()
	if a.count('0') == n:
		print(n * m)
		continue
	if m % 2 == 0:
		a = a + a
	s = list(map(int, list(a)))
	pre = [0] * len(s)
	pre[0] = s[0]
	for i in range(1, len(s)):
		pre[i] = pre[i - 1] + s[i]
	sm = sum(s)
	cnt = 0
	for i in range(len(s)):
		if pre[i] == sm - pre[i]:
			cnt += 1
	print(cnt)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	c_1 = s.count('1')
	c = 0
	if c_1 == 0:
		print(n * m)
	elif c_1 * m % 2 == 1:
		print(0)
	elif m % 2 == 0:
		for i in range(n):
			if s[i] == '0':
				c = c + 1
			else:
				break
		for i in reversed(range(n)):
			if s[i] == '0':
				c = c + 1
			else:
				break
		print(c + 1)
	else:
		summ = 0
		for i in range(n):
			if s[i] == '1':
				summ = summ + 1
			if summ == int(c_1 / 2):
				c = c + 1
		print(c)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	c = input()
	(ones, d, e) = (c.count('1'), 0, 0)
	if ones == 0:
		print(a * b)
	elif ones * b % 2 == 1:
		print(0)
	elif b % 2 == 0:
		i = 0
		while i < a:
			if c[i] == '1':
				break
			d += 1
			i += 1
		j = a - 1
		while j >= 0:
			if c[j] == '1':
				break
			d += 1
			j -= 1
		print(d + 1)
	else:
		i = 0
		while i < a:
			if c[i] == '1':
				e += 1
			if e == ones / 2:
				d += 1
			i += 1
		print(d)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	a = input()
	s = []
	t = 0
	for i in range(n):
		t += int(a[i])
		s.append(t)
	res = 0
	if t == 0:
		print(n * m)
	elif m * t % 2 == 1:
		print(0)
	else:
		for j in range(m):
			pref = j * t
			suf = (m - j - 1) * t
			if abs(suf - pref) <= t:
				for i in range(n):
					if pref + int(s[i]) == suf + t - int(s[i]):
						res += 1
		print(res)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = input()
	p = []
	k = 0
	for i in a:
		k += int(i)
		p.append(k)
	s = [0 for i in range(n)]
	k = 0
	for i in range(n - 1, -1, -1):
		k += int(a[i])
		s[i] = k
	s.append(0)
	if int(a) == 0:
		print(n * m)
	elif m % 2 != 0:
		c = 0
		for i in range(n):
			if p[i] == s[i + 1]:
				c += 1
		print(c)
	else:
		c = 1
		if a[n - 1] == '0':
			for i in range(n - 2, -1, -1):
				c += 1
				if a[i] == '1':
					break
		for i in range(n):
			if a[i] == '1':
				break
			c += 1
		print(c)


t = int(input())

def main(s):
	l = list(s)
	k = l.count('1')
	if k % 2 != 0:
		return 0
	else:
		c = []
		for i in range(len(s)):
			if s[i] == '1':
				c.append(i)
		p = c[len(c) // 2] - c[len(c) // 2 - 1]
		return p
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	x = l[1]
	a = input()
	if a == '0' * n:
		print(n * x)
	else:
		p = main(a)
		s = 2 * a
		q = main(s)
		if x % 2 == 0:
			print(q)
		else:
			print(p)


import sys
from typing import List, Tuple
MAX = sys.maxsize
MIN = -sys.maxsize - 1
BIG = 998244353
MOD = 1000000007

def solve(n: int, m: int, s: str) -> int:
	on = s.count('1')
	ze = s.count('0')
	ans = 1
	if on == 0:
		ans = m * n
	elif on * m % 2 == 1:
		return 0
	elif on % 2 == 1 or m % 2 == 0:
		for i in range(len(s)):
			if s[i] == '0':
				ans += 1
			else:
				break
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '0':
				ans += 1
			else:
				break
	elif m % 2 == 1:
		k = on // 2
		i = 0
		while k:
			if s[i] == '1':
				k -= 1
			i += 1
		while i < len(s):
			if s[i] == '0':
				ans += 1
			else:
				break
			i += 1
	return ans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = input()
	print(solve(n, m, s))


t = int(input())
while t > 0:
	t -= 1
	(N, M) = [int(x) for x in input().split()]
	A = input()
	target = A.count('1') * M
	res = 0
	cc = 0
	start = N * (int(M / 2) - 1)
	cc = target / M * (int(M / 2) - 1)
	end = int(N * M / 2) + N
	if target == 0:
		res = M * N
	elif target % 2 == 0:
		target /= 2
		for i in range(start, end):
			if A[i % N] == '1':
				cc += 1
			if cc == target:
				res += 1
			if cc > target:
				break
	print(res)