Problem: You are given string s of length n consisting of 0-s and 1-s. You build an infinite string t as a concatenation of an infinite number of strings s, or t = ssss ... For example, if s = 10010, then t = 100101001010010...

Calculate the number of prefixes of t with balance equal to x. The balance of some string q is equal to cnt_{0, q} - cnt_{1, q}, where cnt_{0, q} is the number of occurrences of 0 in q, and cnt_{1, q} is the number of occurrences of 1 in q. The number of such prefixes can be infinite; if it is so, you must say that.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".

Input

The first line contains the single integer T (1 ≤ T ≤ 100) — the number of test cases.

Next 2T lines contain descriptions of test cases — two lines per test case. The first line contains two integers n and x (1 ≤ n ≤ 10^5, -10^9 ≤ x ≤ 10^9) — the length of string s and the desired balance, respectively.

The second line contains the binary string s (|s| = n, s_i ∈ \{0, 1\}).

It's guaranteed that the total sum of n doesn't exceed 10^5.

Output

Print T integers — one per test case. For each test case print the number of prefixes or -1 if there is an infinite number of such prefixes.

Example

Input


4
6 10
010010
5 3
10101
1 0
0
2 0
01


Output


3
0
1
-1

Note

In the first test case, there are 3 good prefixes of t: with length 28, 30 and 32.

Solution (in PYTHON3):

Solution:

# Author : raj1307 - Raj Singh
# Date   : 29.01.2020

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii(): return int(input())
def si(): return input()
def mi(): return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li(): return list(mi())

def dmain():
    sys.setrecursionlimit(100000000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import ceil,floor,log,sqrt,factorial
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *,threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 










def main():
        

    
    for _ in range(ii()):
        
        n,x=mi()
        s=list(si())
        if x<0:
            for i in range(n):
                if s[i]=='1':
                    s[i]='0'
                else:
                    s[i]='1'

            x*=-1


        z=s.count('0')
        o=s.count('1')
        d=z-o
        c=[0]*n
        zz=0
        oo=0

        for i in range(n):
            if s[i]=='0':
                zz+=1
            else:
                oo+=1
            c[i]=zz-oo

        f=1
        for i in range(n-1):
            if s[i]==s[i+1]:
                f=0
                break

        """if f==1 and n>1:
            if x==0 or x==1:
                print(-1)
                continue
        """



        if d==0:
            f=0
            for i in range(n):
                if c[i]==x:
                    f=1
                    break

            if f:
                print(-1)
                continue


        ans=0

        if x==0:
            ans+=1

        #print(c)
        if d>=0:
            for i in range(n):

                l=0
                r=10**9

                while l<r:

                    mid=(l+r+1)//2

                    if mid*d+c[i]<=x:
                        l=mid
                        #print(mid,'k')
                    else:
                        r=mid-1

                #print(l*n+i,'j',i,l)
                if l*d+c[i]==x:
                    #print(l*n+i+1,'j')
                    ans+=1
        else:

            for i in range(n):

                l=0
                r=10**9

                while l<r:

                    mid=(l+r+1)//2

                    if mid*d+c[i]<x:
                        r=mid-1
                        #print(mid,'k')
                    else:
                        l=mid

                #print(l*n+i,'j',i,l)
                if l*d+c[i]==x:
                    #print(l*n+i+1,'j')
                    ans+=1


        print(ans)















    






# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
   # read()
    main()
    #dmain()

# Comment Read()