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.*;
 
/* Name of the class has to be "Main" only if the class is public. */
public class Hello
{
	
	public static void main (String[] args) throws IOException
	{
//		Reader s=new Reader();
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pt=new PrintWriter(System.out);
		int T=Integer.parseInt(br.readLine());
		while(T-->0)
		{
		   
		   String s=(br.readLine());
		   StringTokenizer st=new StringTokenizer(s," ");
		   int n=Integer.parseInt(st.nextToken());
		   int x=Integer.parseInt(st.nextToken());
		   s=br.readLine();
		   int arr[]=new int[n];
		   int z=0,o=0;
		   boolean b=false;
		   for(int i=0;i<n;i++) {
			   if(s.charAt(i)=='1')
				   o++;
			   else
				   z++;
			   arr[i]=z-o;
			   if(!b&&arr[i]==x)
				   b=true;
		   }
		   if(arr[n-1]==0&&b)
		   {
			   pt.println(-1);
			   continue;
		   }
		   else if(arr[n-1]==0&&!b)
		   {
			   pt.println(0);
			   continue;
		   }
		   else
		   {
			   int c=0;
			   for(int i=0;i<n;i++)
				   if((x-arr[i])%arr[n-1]==0&&(x-arr[i])/arr[n-1]>=0)
					   c++;
			   if(x==0)
				   c+=1;
			   pt.println(c);
		   }
		}
		  pt.close(); 
	}
	
	static int power(int a,int n, int p) 
    { 
        // Initialize result 
        int res = 1; 
          
        // Update 'a' if 'a' >= p 
        a = a % p;  
      
        while (n > 0) 
        { 
            // If n is odd, multiply 'a' with result 
            if ((n & 1) == 1) 
                res = (res * a) % p; 
      
            // n must be even now 
            n = n >> 1; // n = n/2 
            a = (a * a) % p; 
        } 
        return res; 
    } 
      
    // If n is prime, then always returns true,  
    // If n is composite than returns false with  
    // high probability Higher value of k increases 
    //  probability of correct result. 
    static boolean isPrime(int n, int k) 
    { 
    // Corner cases 
    if (n <= 1 || n == 4) return false; 
    if (n <= 3) return true; 
      
    // Try k times 
    while (k > 0) 
    { 
        // Pick a random number in [2..n-2]      
        // Above corner cases make sure that n > 4 
        int a = 2 + (int)(Math.random() % (n - 4));  
      
        // Fermat's little theorem 
        if (power(a, n - 1, n) != 1) 
            return false; 
      
        k--; 
        } 
      
        return true; 
    }
    static long power(long x, long y, long m)  
    { 
        if (y == 0) 
            return 1; 
          
        long p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        if (y % 2 == 0) 
            return p; 
        else
            return (x * p) % m; 
    } 
      
     
	static int frequency(long arr[], long k)
	{
	    int c=0;
	    for(int i=0;i<arr.length;i++)
	    	if(arr[i]==k)
	    		c++;
	    return c;
	}
	static void remove(long arr[], long k)
	{
	    int i;
	    for(i=0;i<arr.length;i++)
	    	if(arr[i]==k)
	    	{
	    		for(int j=i+1;j<arr.length;j++)
		        arr[j-1]=arr[j];
		        break;
		    }
	}
	void merge(long arr[], int l, int m, int r) 
    { 
        // Find sizes of two subarrays to be merged 
        int n1 = m - l + 1; 
        int n2 = r - m; 
  
        /* Create temp arrays */
        long L[] = new long [n1]; 
        long R[] = new long [n2]; 
  
        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
  
  
        /* Merge the temp arrays */
  
        // Initial indexes of first and second subarrays 
        int i = 0, j = 0; 
  
        // Initial index of merged subarry array 
        int k = l; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
  
        /* Copy remaining elements of L[] if any */
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
  
        /* Copy remaining elements of R[] if any */
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
  
    // Main function that sorts arr[l..r] using 
    // merge() 
    void sort(long arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            // Find the middle point 
            int m = (l+r)/2; 
  
            // Sort first and second halves 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
  
            // Merge the sorted halves 
            merge(arr, l, m, r); 
        } 
    } 
	static class Reader 
    { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    } 
}