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.*; 
import java.util.StringTokenizer; 
import java.io.PrintWriter;
import java.io.*;
import java.util.stream.Collectors.*;
import java.lang.*;
import static java.util.stream.Collectors.*;
import static java.util.Map.Entry.*;
public class Ideo
{ 
    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 int power(int x,int y) 
{ 
    int res = 1;      // Initialize result 
  
      // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y%2==1) 
            res = (res*x); 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x);   
    } 
    return res; 
} 
 
 static long gcd(long a,long b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    } 
 
 
  static boolean compareSeq(char[] S, int x, int y, int n) 
    { 
        for (int i = 0; i < n; i++)
         {
 
            if (S[x] < S[y]) 
               return true;
            else if (S[x] > S[y]) 
                return false; 
            x = (x + 1) % n; 
            y = (y + 1) % n; 
        } 
        return true; 
    } 
 
    static void build(long[] sum,int[] arr,int n)
    {
      for(int i=0;i<(1<<n);i++)
      {
        long total=0;
        for(int j=0;j<n;j++)
        {
          if((i & (1 << j)) > 0)
            total+=arr[j];
        }
 
        sum[i]=total;
      }
    }

 
       static int parity(int a)
       {
    a^=a>>16;
    a^=a>>8;
    a^=a>>4;
    a^=a>>2;
    a^=a>>1;
    return a&1;
  }
/*
  PriorityQueue<aksh> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.p < o2.p)
                return 1;
            else if (o1.p > o2.p)
                return -1;
            else
                return 0;
 
        });//decreasing order acc to p*/
static int power(int x, int y, int m)  
    { 
        if (y == 0) 
            return 1; 
          
        int p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        if (y % 2 == 0) 
            return p; 
        else
            return (x * p) % m; 
    } 
/*static int modinv(int a, int m) 
    { 
        int g = gcd(a, m); 
        if (g != 1) 
            return 0;
        else 
        { 
           return power(a, m - 2, m); 
        } 
        //return 0;
    } */
 
static int[] product(int[] nums) {
    int[] result = new int[nums.length];
 
    int[] t1 = new int[nums.length];
    int[] t2 = new int[nums.length];
 
    t1[0]=1;
    t2[nums.length-1]=1;
 
    //scan from left to right
    for(int i=0; i<nums.length-1; i++){
        t1[i+1] = nums[i] * t1[i];
    }
 
    //scan from right to left
    for(int i=nums.length-1; i>0; i--){
        t2[i-1] = t2[i] * nums[i];
    }
 
    for(int i=0;i<nums.length;i++)
      {
        System.out.print(t1[i]+" "+t2[i]);
        System.out.println();
      }
 
    //multiply
    for(int i=0; i<nums.length; i++){
        result[i] = t1[i] * t2[i];
    }
 
    return result;
}
 
static int getsum(int[] bit,int ind)
{
  int sum=0;
  while(ind>0)
  {
    sum+=bit[ind];
    ind-= ind & (-ind);
  }
 
  return sum;
}
 
static void update(int[] bit,int max,int ind,int val)
{
  while(ind<=max)
  {
    bit[ind]+=val;
    ind+= ind & (-ind);
  }
}
 
    //static ArrayList<Integer>[] adj;
 
    static boolean check(long mid,long a,long b)
    {
      long count=1;
      while(count<=mid)
      {
        count++;
        if(a<b)
          a+=count;
        else
          b+=count;
 
        if(a==b)
          return true;
      }
        return false;
    }
 
    static class aksh implements Comparable<aksh>
    {
      int x;
      int y;
 
      public aksh(int x,int y)
      {
        this.x=x;
        this.y=y;
      }
 
      public int compareTo(aksh o)
      {
        if(x!=o.x)
          return x-o.x;
        else
          return y-o.y;
      }
    }
    static int get(int arr[], int n) 
    { 
        int result = 0; 
        int x, sum; 
          
        // Iterate through every bit 
        for(int i=0; i<32; i++) 
        { 
            // Find sum of set bits at ith position in all  
            // array elements 
            sum = 0; 
            x = (1 << i); 
            for(int j=0; j<n; j++) 
            { 
                if((arr[j] & x)!=0) 
                sum++; 
            } 
            // The bits with sum not multiple of 3, are the 
            // bits of element with single occurrence. 
            if ((sum % 3)!=0) 
            result |= x; 
        } 
        return result; 
    } 
    /*        Collections.sort(orders, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                if (o1.diff < o2.diff) {
                    return -1;
                } else if (o1.diff > o2.diff) {
                    return 1;
                } else {
                    return 0;
                }
            }
        });  */
 
 
    static boolean isPrime(int n)  
    {  
        // Corner cases  
        if (n <= 1) return false;  
        if (n <= 3) return true;  
          
        // This is checked so that we can skip  
        // middle five numbers in below loop  
        if (n % 2 == 0 || n % 3 == 0) return false;  
          
        for (int i = 5; i * i <= n; i = i + 6)  
            if (n % i == 0 || n % (i + 2) == 0)  
            return false;  
          
        return true;  
    }  
      
    static int nextPrime(int N)  
    {  
      
        // Base case  
        if (N <= 1)  
            return (2-N);  
      
        int prime = N;  
        boolean found = false;  
      
        // Loop continuously until isPrime returns  
        // true for a number greater than n  
        while (!found)  
        {  
            if (isPrime(prime))  
                {
                  found = true;
                  break;
                }  
 
            prime++;
        }  
      
        return (prime-N);  
    }  
 
 
    static long product(long x) 
{ 
    long prod = 1; 
    while (x > 0)  
    { 
        prod *= (x % 10); 
        x /= 10; 
    } 
    return prod; 
} 
  
// This function returns the number having 
// maximum product of the digits 
static long findNumber(long l, long r) 
{ 
    // Converting both integers to strings 
    //string a = l.ToString(); 
    String b = Long.toString(r); 
  
    // Let the current answer be r 
    long ans = r; 
    for (int i = 0; i < b.length(); i++)  
    { 
        if (b.charAt(i) == '0') 
            continue; 
  
        // Stores the current number having 
        // current digit one less than current 
        // digit in b 
        char[] curr = b.toCharArray(); 
        curr[i] = (char)(((int)(curr[i] -  
                    (int)'0') - 1) + (int)('0')); 
  
        // Replace all following digits with 9 
        // to maximise the product 
        for (int j = i + 1; j < curr.length; j++) 
            curr[j] = '9'; 
  
        // Convert string to number 
        int num = 0; 
        for (int j = 0; j < curr.length; j++) 
            num = num * 10 + (curr[j] - '0'); 
  
        // Check if it lies in range and its product 
        // is greater than max product 
        if (num >= l && product(ans) < product(num)) 
            ans = num; 
    } 
  
    return product(ans); 
} 
 
static long mod=998244353;
 
static long pow(long in, long pow) {
    if(pow == 0) return 1;
    long out = pow(in, pow / 2);
    out = (out * out) % mod;
    if(pow % 2 == 1) out = (out * in) % mod;
    return out;
  }
  static long inv(long in) {
    return pow(in, mod - 2);
  }
 
  static void swap(int x,int y)
  {
    int temp=x;
    x=y;
    y=temp;
  }
 
  static int[] par;
  static int[] size;
  static int find(int i) 
  {
     if (par[i] == i)
      return i;
 
    return par[i] = find(par[par[i]]);
  }
 
  static void union(int x, int y) 
  {
      x = find(x);
      y = find(y);
      if (x == y)
        return;
      if (size[x] < size[y])
        swap(x, y);
 
      par[y] = x;
      size[x] += size[y];
    }
 
 
    static void multisourcebfs(long[] arr,int n,int m)
    {
      //HashSet<Long> vis=new HashSet<>();
      HashMap<Long,Long> dis=new HashMap<>();
      Queue<Long> q=new LinkedList<>();
 
      for(int i=0;i<arr.length;i++)
      {
        dis.put(arr[i],(long)0);
        q.add(arr[i]);
        //vis.add(arr[i]);
      }
 
      long[] res=new long[m];
      long ans=0;
      int k=0;
      while(!q.isEmpty())
      {
        if(k==m)
          break;
        long x=q.remove();
        if(dis.get(x)!=0)
        {
          ans+=dis.get(x);
          res[k]=x;
          k++;
        }
 
        if(dis.get(x-1)==null)
        {
          dis.put(x-1, dis.get(x)+1);
          q.add(x-1);
          //vis.add(x-1);
        }
 
        if(dis.get(x+1)==null)
        {
          dis.put(x+1, dis.get(x)+1);
          q.add(x+1);
          //vis.add(x+1);
        }
      }
 
      System.out.println(ans);
 
      for(int i=0;i<m;i++)
        System.out.print(res[i]+" ");
 
    }
 
    static int x; 
    static int maxcount=0;
    static void dfs(int node,int par,int dist)
    {
        if(dist>=maxcount)
        {
           maxcount=dist;
           x=node;
        }
 
        List<Integer> l = adj[node]; 
        for(Integer i: l)
        {
          if(i!=par)
          dfs(i,node,dist+1);
        }
    }

    

    static int h;
    static int w;
    static int bfs(char[][] ch,int i,int j)
    {
        Queue<aksh> q=new LinkedList<>();
        q.add(new aksh(i,j));

        int[][] dis=new int[h][w];
        int[][] vis=new int[h][w];
        vis[i][j]=1;
        dis[i][j]=0;
 
        while(!q.isEmpty())
        {
          aksh arr=q.poll();
          int x1=arr.x;
          int y1=arr.y;
 
          if((x1-1)>=0 && ch[x1-1][y1]!='#' && vis[x1-1][y1]==0)
          {
            vis[x1-1][y1]=1;
            q.add(new aksh(x1-1, y1));
            dis[x1-1][y1]=Math.max(dis[x1-1][y1],dis[x1][y1]+1);
          }
 
          if((x1+1)<h && ch[x1+1][y1]!='#' && vis[x1+1][y1]==0)
          {
            vis[x1+1][y1]=1;
            dis[x1+1][y1]=Math.max(dis[x1+1][y1],dis[x1][y1]+1);
            q.add(new aksh(x1+1, y1));
          }
 
          if((y1-1)>=0 && ch[x1][y1-1]!='#' && vis[x1][y1-1]==0)
          {
            vis[x1][y1-1]=1;
            dis[x1][y1-1]=Math.max(dis[x1][y1-1],dis[x1][y1]+1);
            q.add(new aksh(x1,y1-1));
          }
 
    
          if((y1+1)<w && ch[x1][y1+1]!='#' && vis[x1][y1+1]==0)
          {
            vis[x1][y1+1]=1;
            dis[x1][y1+1]=Math.max(dis[x1][y1+1],dis[x1][y1]+1);
            q.add(new aksh(x1,y1+1));
          }
        }
        int max=Integer.MIN_VALUE;

        for(int x=0;x<h;x++)
        {
          for(int y=0;y<w;y++)
            max=Math.max(dis[x][y],max);
        }

        return max;
    }

    static ArrayList<Integer> cnt;

    static void primefact(int n)
    {
 
          for (int i=2;i*i<=n;i++)
           {
              while ((n % i)==0)
              {
                cnt.add(i);
                n /= i;
              }
           }

          if(n>1)
             {
              cnt.add(n);
             }
    }

    static boolean hash[];
    static void sieve(int n)
    {
      Arrays.fill(hash, true);
    for (int p = 2; p * p < n; p++) 
        if (hash[p] == true) 
            for (int i = p * 2; i < n; i += p) 
                hash[i] = false; 
    }

    static long div(long n) 
  {
    long total = 1; 
    for (int p = 2; p <= n; p++)  
    { 
        if (hash[p]) 
        { 
            int count = 0; 
            if (n % p == 0)  
            { 
                while (n % p == 0)  
                { 
                    n = n / p; 
                    count++; 
                } 
                total = total * (count + 1); 
            } 
        } 
    } 
    return total; 
} 


    static void SieveOfEratosthenes(long n, boolean prime[], 
                                    boolean primesquare[], int a[]) 
    { 
        // Create a boolean array "prime[0..n]" and 
        // initialize all entries it as true. A value 
        // in prime[i] will finally be false if i is 
        // Not a prime, else true. 
        for (int i = 2; i <= n; i++) 
            prime[i] = true; 
  
        /* Create a boolean array "primesquare[0..n*n+1]" 
         and initialize all entries it as false. 
         A value in squareprime[i] will finally  
         be true if i is square of prime,  
         else false.*/
        for (int i = 0; i < ((n * n) + 1); i++) 
            primesquare[i] = false; 
  
        // 1 is not a prime number 
        prime[1] = false; 
  
        for (int p = 2; p * p <= n; p++) { 
            // If prime[p] is not changed, 
            // then it is a prime 
            if (prime[p] == true) { 
                // Update all multiples of p 
                for (int i = p * 2; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
  
        int j = 0; 
        for (int p = 2; p <= n; p++) { 
            if (prime[p]) { 
                // Storing primes in an array 
                a[j] = p; 
  
                // Update value in 
                // primesquare[p*p], 
                // if p is prime. 
                primesquare[p * p] = true; 
                j++; 
            } 
        } 
    } 
  
    // Function to count divisors 
    static boolean countDivisors(long n) 
    { 
        // If number is 1, then it will 
        // have only 1 as a factor. So, 
        // total factors will be 1. 
        if (n == 1) 
            return false; 
  
        boolean prime[] = new boolean[(int)n + 1]; 
        boolean primesquare[] = new boolean[(int)(n * n) + 1]; 
  
        // for storing primes upto n 
        int a[] = new int[(int)n]; 
  
        // Calling SieveOfEratosthenes to 
        // store prime factors of n and to 
        // store square of prime factors of n 
        SieveOfEratosthenes(n, prime, primesquare, a); 
  
        // ans will contain total number 
        // of distinct divisors 
        int ans = 1; 
  
        // Loop for counting factors of n 
        for (int i = 0;; i++) { 
            // a[i] is not less than cube root n 
            if (a[i] * a[i] * a[i] > n) 
                break; 
  
            // Calculating power of a[i] in n. 
            // cnt is power of prime a[i] in n. 
            int cnt = 1; 
  
            // if a[i] is a factor of n 
            while (n % a[i] == 0) { 
                n = n / a[i]; 
  
                // incrementing power 
                cnt = cnt + 1; 
            } 
            ans = ans * cnt; 
        } 
  
        // if a[i] is greater than cube root 
        // of n 
  
        // First case 
        if (prime[(int)n]) 
            ans = ans * 2; 
  
        // Second case 
        else if (primesquare[(int)n]) 
            ans = ans * 3; 
  
        // Third casse 
        else if (n != 1) 
            ans = ans * 4; 
  
        return prime[ans]; // Total divisors 
    } 


    static final long INF = Long.MAX_VALUE/5;
    static ArrayList<Integer>[] adj;
    public static void main(String args[] ) throws Exception 
    {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
 
        FastReader sc=new FastReader();
        int t=sc.nextInt();

        while(t-->0)
        {
          int n=sc.nextInt();
          int x=sc.nextInt();
          String s=sc.next();
          HashMap<Integer,Integer> cnt=new HashMap<>();
   
          int cur = 0;

         for(int i=0;i<s.length();i++)
        {
          char ch=s.charAt(i);
          if(ch == '0')
            cur++;
          else
            cur--;

          if(cnt.get(cur)==null)
            cnt.put(cur,1);
          else
            cnt.put(cur,cnt.get(cur)+1);
        }

        if(cur == 0)
      if (cnt.containsKey(x))
        System.out.println("-1");
      else
        System.out.println("0");

    else
    {
      int ans = 0;
      int mdvl = x % cur;

        Iterator it = cnt.entrySet().iterator();
    while (it.hasNext()) 
    {
        Map.Entry a= (Map.Entry)it.next();
        int x1=(int)a.getKey();
        int x2=(int)a.getValue();
        int k = (x - x1) / cur;

        int val = x - k * cur;

        if (val != x1 || k < 0)
          continue;

        ans += x2;
    }

      if (x == 0)
        ans++;

     System.out.println(ans);
     }
          

        }

        
        }
 
    }