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:
import java.util.*;
import java.io.*;
public class main {
	static class pair implements Comparable<pair>{
		int a;int b;
		public pair(int a, int b) {
			this.a=a;
			this.b=b;
		}
        public int compareTo(pair p){
        	return(a-p.a==0)?b-p.b:a-p.a;
        }
        public String toString () {
        	return a+" "+b;
        }
	}
  public static void main(String[] args) throws IOException {
	  
	  Scanner sc = new Scanner(System.in);
	  PrintWriter out = new PrintWriter(System.out);
	  int t = sc.nextInt();
	  while(t-->0) {
		 int n = sc.nextInt();
		 int x = sc.nextInt();
		 char [] arr= sc.nextLine().toCharArray();
		 int [] sum = new int[n];
		 int c =0;
		 int numz=0;
		 if(x==0) c++;
		 sum[0]= arr[0]=='0'?1:-1;
		 if(sum[0]==x) c++;
		 for(int i=1; i<n; i++) {sum[i] = sum[i-1]+ (arr[i]=='0'?1:-1);
		 if(sum[i]==x) c++;
		 if(sum[i]==0) numz++;}
		 int last = sum[n-1];
		 if(last==0&&c!=0) out.println(-1);
		 else if(last==0&&c==0) out.println(0);
		 else {
			 if(x>=0&&last>0) {
		for(int i=0; i<n; i++) {
			if(x-sum[i]>0&&(x-sum[i])%last==0) c++;
		}}
			 else if(x>=0&&last<0) {
				 for(int i=0; i<n; i++) {
						if(sum[i]-x>0&&(sum[i]-x)%(-1*last)==0) c++;
					} 
			 }else if(x<0&&last>0) {
				 for(int i=0; i<n; i++) {
						if(x-sum[i]>0&&(x-sum[i])%last==0) c++;
					}
			 }
			 else if(x<0&&last<0) {
				 for(int i=0; i<n; i++) {
						if(sum[i]-x>0&&(sum[i]-x)%(-1*last)==0){ c++;}
					}  
			 }
			 out.println(c);
		 }
	  }
	  out.flush();
 
}
 
 
 static class Scanner 
  {
  	StringTokenizer st;
  	BufferedReader br;
 
  	public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
 
  	public String next() throws IOException 
  	{
  		while (st == null || !st.hasMoreTokens()) 
  			st = new StringTokenizer(br.readLine());
  		return st.nextToken();
  	}
 
  	public int nextInt() throws IOException {return Integer.parseInt(next());}
  	
  	public long nextLong() throws IOException {return Long.parseLong(next());}
 
  	public String nextLine() throws IOException {return br.readLine();}
  	
  	public double nextDouble() throws IOException
  	{
  		String x = next();
  		StringBuilder sb = new StringBuilder("0");
  		double res = 0, f = 1;
  		boolean dec = false, neg = false;
  		int start = 0;
  		if(x.charAt(0) == '-')
  		{
  			neg = true;
  			start++;
  		}
  		for(int i = start; i < x.length(); i++)
  			if(x.charAt(i) == '.')
  			{
  				res = Long.parseLong(sb.toString());
  				sb = new StringBuilder("0");
  				dec = true;
  			}
  			else
  			{
  				sb.append(x.charAt(i));
  				if(dec)
  					f *= 10;
  			}
  		res += Long.parseLong(sb.toString()) / f;
  		return res * (neg?-1:1);
  	}
  	
  	public boolean ready() throws IOException {return br.ready();}
 
 
  }
 static void shuffle(int[] a)
	{
		int n = a.length;
		for(int i = 0; i < n; i++)
		{
			int r = i + (int)(Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
}