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:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    T = I()
    n = [0] * T
    x = [0] * T
    s = [''] * T

    for i in range(T):
        n[i], x[i] = MI()
        s[i] = S()

    for t in range(T):
        Q = s[t]
        X = x[t]
        one = 0
        zero = 0
        ans = 0
        a = [0] * (len(Q) + 1)
        for i in range(len(Q)):
            if Q[i] == '1':
                one += 1
            else:
                zero += 1
            a[i+1] += zero - one

        for i in range(len(a)):
            if a[i] == X:
                ans += 1
        end = a[-1]
        # print(Q, X, a, end)

        if end == 0 and ans != 0:
            print(-1)
            continue

        if end == 0 and ans == 0:
            print(0)
            continue

        for i in range(1, len(a)):
            if end > 0 and a[i] < X and ((X - a[i]) % end) == 0:
                # print(X, a[i])
                ans += 1
            elif end < 0 and a[i] > X and ((a[i] - X) % abs(end)) == 0:
                ans += 1

        print(ans)


    # for i in range(T):
    #     m = {1: 0, 0: 0}
    #     q = s[i]
    #     for k in range(len(q)):
    #         m[int(q[k])] += 1
    #     a = m[0] - m[1]

    #     if a == 0 and a == x[i]:
    #         print(-1)
    #         continue

    #     if a == 0:
    #         blance = 0
    #         ans = 0
    #         for j in range(len(q)):
    #             if q[j] == '0':
    #                 blance += 1
    #             else:
    #                 blance -= 1
    #             # print(q[j], blance, x[i])
    #             if blance == x[i]:
    #                 ans += 1
    #         if ans > 0:
    #             print(-1)
    #             continue

    #     if a < 0 and x[i] > 0 or a > 0 and x[i] < 0:
    #         print(0)
    #         continue

    #     if a == 0 and a != x[i]:
    #         print(0)
    #         continue

    #     m = {}
    #     blance = 0
    #     high = 0
    #     for j in range(len(q)):
    #         if q[j] == '0':
    #             blance += 1
    #         else:
    #             blance -= 1
    #         # print(q[j], blance)
    #         if blance not in m:
    #             m[blance] = 1
    #             high = max(high, abs(blance))
    #         else:
    #             m[blance] += 1
    #             high = max(high, abs(blance))
    #     print(m, high)

    #     c = 1
    #     while True:
    #         tmp = x[i] + high
    #         for num, v in m.items():
    #             num * c
    #         c += 1
    #         if a * c > x[i] + high:
    #             break


    #     repeat = x[i] // a
    #     ans = 0
    #     blance = a * (repeat - 1)
    #     q = q * 2
    #     for j in range(len(q)):
    #         if q[j] == '0':
    #             blance += 1
    #         else:
    #             blance -= 1
    #         # print(q[j], blance)
    #         if blance == x[i]:
    #             ans += 1
    #     print(ans)

        # for i in range()
        # print(q, a, repeat, x[i])
        # tmp = ''
        # for j in range(len(st)):
        #     tmp += st[j]
        #     m = {1: 0, 0: 0}
        #     if m[0] - m[1] == 10:
        #         print(len(tmp), m[0] - m[1])


if __name__ == '__main__':
    main()