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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;

public class InfinitePrefixes_CodeForces {
	public static void main(String[]args) throws NumberFormatException, IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		int t=Integer.parseInt(br.readLine());
		for(int j=0;j<t;j++){
			String[]r= br.readLine().split(" ");
			int n=Integer.parseInt(r[0]);
			long x=Integer.parseInt(r[1]);
			String s=br.readLine();	
			long count0=0;
			long count1=0;
			ArrayList <Integer>h = new ArrayList<Integer>();
			int n0=0;
			int n1=0;
			h.add(0);
			for(int i=0;i<s.length()-1;i++){
				if(s.charAt(i)=='0')
					n0++;
				else
					n1++;
				h.add(n0-n1);
			}
			//System.out.println(h);
			//System.out.println("the x is "+x);
			if(s.charAt(s.length()-1)=='0')
				n0++;
			else
				n1++;
			int diff=n0-n1;
			//System.out.println("the diff is "+diff);
			long ans=0;
			//if(diff==x)
				//out.println(-1);
			//else
				if (diff==0){
				//System.out.println("I am here 1");
				boolean flag=true;
				for(int l:h){
					if(l==x){
						flag=false;
					//	System.out.println("I am here 2");
					//	out.println(-1);
					}
				}
				if(!flag)
					out.println(-1);
				if(flag)
					out.println(0);
			}
			else{
				for(int l:h){
					if(diff!=0 &&(x-l)%diff==0 && (x-l)*diff>=0){
						ans++;
						//System.out.println("the l is "+l);
						//System.out.println("the upper part is "+ (x-l));
						//System.out.println("the diff is "+ diff);
					}
				}
				out.println(ans);

			}
		}
		out.flush();
		out.close();

	}



	//	public static void main(String[]args) throws NumberFormatException, IOException{
	//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	//		PrintWriter out = new PrintWriter(System.out);
	//		int t=Integer.parseInt(br.readLine());
	//		for(int j=0;j<t;j++){
	//			//System.out.println("the j is "+j);
	//			String[]r= br.readLine().split(" ");
	//			int n=Integer.parseInt(r[0]);
	//			long x=Integer.parseInt(r[1]);
	//			String s=br.readLine();
	//			long count0=0;
	//			long count1=0;
	//			StringBuilder res=new StringBuilder("");
	//			for(int i=0;i<s.length();i++){
	//				if(s.charAt(i)=='0')
	//					count0++;
	//				else
	//					count1++;
	//			}
	//			if(count0-count1==x){
	//				out.println(-1);
	//				//out.flush();
	//				//out.close();
	//				//System.exit(0);
	//			}
	//			
	//			else{
	//			long n0=0;
	//			long n1=0;
	//			long count=0;
	//			long ans=0;
	//			if(x>0 && count0<x){
	//				int y=(int)(x/(count0==count1?count0-count1+1:count0-count1));
	//				y=Math.abs(y);
	//				y--;
	//				count+=y;
	//				n0+=(count0*y);
	//				n1+=(count1*y);
	//				
	//			}
	//			else if(x<0 && count1<(x*-1)){
	//				int y=(int)((x*-1)/(count0==count1?count1-count0+1:count1-count0));
	//				y=Math.abs(y);
	//				y--;
	//				count+=y;
	//				n0+=(count0*y);
	//				n1+=(count1*y);
	//				
	//			}
	//			System.out.println("The first count is "+count);
	//			while(s.length()*count<=1e9){
	//				System.out.println(count);
	//				n0+=count0;
	//				n1+=count1;
	//				count++;
	//				if(n0-n1==x){
	//					//System.out.println(count);
	//					ans++;
	//				}
	//				long temp0=0;
	//				long temp1=0;
	//				String tempo="";
	//				for(int i=0;i<s.length()-1;i++){
	//					tempo+=s.charAt(i);
	//					if(s.charAt(i)=='0'){
	//						temp0++;
	//					}
	//					else 
	//						temp1++;
	//					if((n0+temp0)-(n1+temp1)==x){
	//						//System.out.println("the count is " +count );
	//						//System.out.println("the part is "+(i+1));
	//						//System.out.println(tempo);
	//						ans++;
	//					}
	//				}
	//				
	//			}
	//			if(x==0)
	//				ans+=1;
	//			out.println(ans);
	//			
	//		}
	//			}
	//		out.flush();
	//		out.close();
	//	}

}