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 JAVA):

Solution:
// package may2020;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class C {
//	@SuppressWarnings("unchecked")
	static long x,y;
	static long ans=0;
	public static void main(String[] args) throws IOException {
		FastReader scn = new FastReader();
		OutputStream out = new BufferedOutputStream(System.out);
		int t=scn.nextInt();
		int[] sw = {6,2,5,5,4,5,6,3,7,6};
		Here:
		while(t-->0) {
			int n =scn.nextInt(),x = scn.nextInt();
			
			char[] s = scn.next().toCharArray();
			int[] c0 = new int[n];
			int[] c1 = new int[n];
			for(int i=0;i<n;i++) {
				if(s[i]=='0') {
					c0[i]=(i==0?0:c0[i-1])+1;
					c1[i]=(i==0?0:c1[i-1]);
				}else {
					c1[i]=(i==0?0:c1[i-1])+1;
					c0[i] = (i==0?0:c0[i-1]);
				}
			}
			boolean ok = false;
			for(int i=0;i<n;i++) {
				if(c0[i]==c1[i]+x) {
					ok=true;
				}
			}
			if(c0[n-1]==c1[n-1]&&ok) {
				out.write("-1\n".getBytes());
				continue Here;
			}
			int[] bal = new int[n+1];
			
			for(int i=1;i<=n;i++) {
				bal[i]= c0[i-1]-c1[i-1];
			}
			
			int ans =0;
			if(bal[n]!=0) {
				for(int i=0;i<n;i++) {
					if(Math.abs(x-bal[i])%Math.abs(bal[n])==0) {
						if((x-bal[i])/bal[n]>=0)
							ans++;
					}
				}
			}
			
			
			out.write((ans+"\n").getBytes());
//			out.flush();
		}
		out.close();
	}
//	static long search(int m,int n) 
//    { 
//        long ans = 1; 
//        for (long i = n; i < ((long)m + (long)n - 1); i++) { 
//            ans *= i; 
//            ans /= (i - n + 1); 
//        } 
//        return ans; 
//    } 
	public static int[] merge(int[] one,int[] two){
		int[] res = new int[one.length+two.length];
		int i = 0;
		int j = 0;
		int k = 0;
		
		while(i<one.length&&j<two.length){
			if(one[i]<two[j]){
				res[k] = one[i];
				i++;
				k++;
			}
			else{
				res[k] = two[j];
				j++;
				k++;
			}
		}
		
		if(i==one.length){
			while(j<two.length){
				res[k] = two[j];
				j++;
				k++;
			}
		}
		else{
			while(i<one.length){
				res[k] = one[i];
				k++;
				i++;
			}
		}
		return res;
	}
	public static int[] mergesort(int[] arr, int l, int r){
		if(l==r){
			int[] br = new int[1];
			br[0] = arr[l];
			return br;
		}
		int mid = (l+r)/2;
		int[] fh = mergesort(arr,l,mid);
		int[] sh = mergesort(arr,mid+1,r);
		
		return merge(fh,sh);
	}

//	public static long lcm(long a,long b) {
//		return a/gcd(a,b)*b;
//	}
//	public static long gcd(long a,long b) {
//		if(a == 0)
//			return b;
//		return gcd(b%a,a);
//	}
//	public static int[] merge(int[] one,int[] two){
//		int[] res = new int[one.length+two.length];
//		int i = 0;
//		int j = 0;
//		int k = 0;
//		
//		while(i<one.length&&j<two.length){
//			if(one[i]<two[j]){
//				res[k] = one[i];
//				i++;
//				k++;
//			}
//			else{
//				res[k] = two[j];
//				j++;
//				k++;
//			}
//		}
//		
//		if(i==one.length){
//			while(j<two.length){
//				res[k] = two[j];
//				j++;
//				k++;
//			}
//		}
//		else{
//			while(i<one.length){
//				res[k] = one[i];
//				k++;
//				i++;
//			}
//		}
//		return res;
//	}
//	public static int[] mergesort(int[] arr, int l, int r){
//		if(l==r){
//			int[] br = new int[1];
//			br[0] = arr[l];
//			return br;
//		}
//		int mid = (l+r)/2;
//		int[] fh = mergesort(arr,l,mid);
//		int[] sh = mergesort(arr,mid+1,r);
//		
//		return merge(fh,sh);
//	}
//	static int ub(int[] a, int val) {
//		int l=0, r=a.length;
//		
//		while(r>l) {
//			int x = (r+l)>>1;
//			if(val>=a[x]) {
//				l=x+1;
//			}else {
//				r=x;
//			}
//		}
//		return l;
//	}
//	static int lb(int[] a, int val) {
//		int l = 0;
//		int r = a.length;
//		while(r>l) {
//			int x = (l+r)>>1;
//			if(a[x]>=val) {
//				r=x;
//			}else {
//				l=x+1;
//			}
//		}
//		return l;
//	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

}