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.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
 
public class hello
 {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; 
           } 
         
       }
    
    static String sum (String s)
    {
        String s1 = ""; 
        
        if(s.contains("a"))
            s1+="a";
        if(s.contains("e"))
            s1+="e";
        if(s.contains("i"))
            s1+="i";
        if(s.contains("o"))
            s1+="o";
        if(s.contains("u"))
            s1+="u";
        
            return s1;
            
        
    }
    
 
    public static HashMap<String, Integer> sortByValue(HashMap<String, Integer> hm) 
    { 
        // Create a list from elements of HashMap 
        List<Map.Entry<String, Integer> > list = 
               new LinkedList<Map.Entry<String, Integer> >(hm.entrySet()); 
  
        // Sort the list 
        Collections.sort(list, new Comparator<Map.Entry<String, Integer> >() { 
            public int compare(Map.Entry<String, Integer> o1,  
                               Map.Entry<String, Integer> o2) 
            { 
                return (o1.getValue()).compareTo(o2.getValue()); 
            } 
        }); 
          
        // put data from sorted list to hashmap  
        HashMap<String, Integer> temp = new LinkedHashMap<String, Integer>(); 
        for (Map.Entry<String, Integer> aa : list) { 
            temp.put(aa.getKey(), aa.getValue()); 
        } 
        return temp; 
    } 
    
    
public static void main(String args[])
    {
        FastReader input =new FastReader();
      
        
        
        int p = input.nextInt();
        
        
        while(p-->0)
        {
        	 
        	
        	int n = input.nextInt();
        	
        	int x = input.nextInt();
        	
        	
        	String s = input.next();
        	int a[] = new int[n];
        	int sum =0;
        	for(int i=0;i<s.length();i++)
        	{
        		if(s.charAt(i)=='1')
        			a[i] = -1;
        		else
        			a[i] =  1;
        		
        		
        		sum+=a[i];
        	}
        	
       // 	for(int i=0;i<s.length();i++)
        //	{
        	//	System.out.print(a[i] + " ");
        	//}
        	
        	
        	int pre[] = new int[n];
        	
        	
        
        	int pre1[] = new int[n];
        	pre1[0] = a[0];
        	int min = pre1[0];
        	int z=0;
        	int max = pre1[0];
        	int z1 =0;
        	
        	HashSet<Integer> set = new HashSet<Integer>();
        	set.add(pre1[0]);
        	
        
        	
        	
        	
        	
        	
        	
        	
        	
        	
        	for(int i=1;i<n;i++)
        	{
        		
        		pre1[i]=  pre1[i-1]+a[i];
        		if(min>=pre[i])
        		{
        			min = pre[i];
        			z= i;
        		}
        		
        		if(max<=pre[i])
        		{
        			max = pre[i];
        			z1=i;
        		}
        		set.add(pre1[i]);
        		
        	}
       /* 	System.out.println();
        	for(int i=0;i<s.length();i++)
        	{
        		System.out.print(pre1[i] + " ");
        	}
        	
        	
        	
        	System.out.println();
        */
        	int i=0;
        	int count =0;
        	
        	
        	pre[0] = a[0];
        	int flag=-1;
        	if(sum>0)
        	{
        		flag=1;
        	}
        	else if(sum<0)
        	{
        		flag=0;
        	}
        	
        	
	
        	
        	if(sum==0)
        	{
        		if(set.contains(x))
        		{
        			System.out.println(-1);
        		}
        		else
        			{
        				for(int j=0;j<n;j++)
        				{
        					if(pre1[j]==x)
        						count++;
        				}
        				
        					System.out.println(count);
        			}
        	}
        	else
        	{

        		for (i=0;i<n;i++)
                {
                    int check=x-pre1[i];
                    if(check<0 && sum>0) continue;
                    else if(check>0 && sum<0) continue;
                    if(check%sum==0) count++; 
                }
                if(x==0 ) count++;

        		

            	System.out.println(count);
        		
        	}
        	
       
        }
        	
        }
        
        
        
        
        
    
        
      
        
   
        
        
        
        
        
  
	

	
 
 
static boolean find(int a[],int A,int B)
	{
		if( root(a,A)==root(a,B) )       //if A and B have the same root, it means that they are connected.
			return true;
		else
			return false;
	}
 
 
 
 
 
	static void union(int Arr[],int size[],int A,int B)
	{
		int root_A = root(Arr,A);
		int root_B = root(Arr,B);
		
		
		if(root_A == root_B)
		{
			return;
		}
		if(size[root_A] < size[root_B] )
		{
			Arr[ root_A ] = Arr[root_B];
			size[root_B] += size[root_A];
			size[root_A] = 0;	
			
		}
		else
		{
			Arr[ root_B ] = Arr[root_A];
			size[root_A] += size[root_B];
			size[root_B] = 0;
			
 
			
			
			
		}
 
	}
	
	
	
	static int root (int Arr[ ] ,int i)
	{
		while(Arr[ i ] != i)          
        {
			i = Arr[ i ];
        }
        return i;
	}
	static long factorial(long n)
    {
        long fact = 1;
        for(int i=1;i<=n;i++)
        {
            fact*=i;
        }
        return fact;
    }
 }
 
 
 class Pair
 {
     int a;
     int b;
     Pair(int a,int b)
     {
         this.a=a;
         this.b=b;
     }
 }