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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.util.*;
 
public class A3 {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        solve(in, out);
        out.close();
    }
 
    public static void solve(InputReader sc, PrintWriter pw) {
        int i,j=0;
        // int t=1;
        int t=sc.nextInt();
        u:while(t-->0){
            long n=sc.nextLong();
            long x=sc.nextLong();
            String s=sc.next();
            char ch[]=s.toCharArray();
            long p[]=new long[(int)n+1];
            HashMap<Long,Long> map=new HashMap<>();
            map.put(0L,0L);
            long min=0,max=0;
            for(i=1;i<=n;i++){
                p[i]=p[i-1]+((ch[i-1]=='0')?1:-1);
                if(x<0){
                    p[i]=p[i-1]+((ch[i-1]=='0')?-1:1);
                }
                // pw.println("**"+p[i]);
                min=Math.min(min,p[i]);
                max=Math.max(max,p[i]);
                if(map.containsKey(p[i])){
                    map.put(p[i],map.get(p[i])+1);
                    // pw.println("%"+p[i]+" "+map.get(p[i]));
                }
                else{
                    map.put(p[i],1L);
                }
            }
            x=Math.abs(x);
            long last=p[(int)n];
            if(last==0&&map.containsKey(x)){
                pw.println("-1");
            }
            else if(last==0){
                pw.println("0");
            }
            else if(last<0&&x>max){
                pw.println("0");
            }
            else{
                long h=x,c=0;
                if(h==0)
                    c+=1;
                if(h>max&&last>0){
                    long jj=last;
                    h=h%jj+(max-max%jj)+jj;
                }
                else if(h<min&&last<0){
                    long jj=-1*last;
                    long m=min/jj-2;
                    h+=m*jj;
                    // h=h%last+(min-min%last)-2*last;
                }
                // pw.println(h+" "+max+" "+min);
                while((last>0&&h>=min)||(last<0&&h<=max)){
                    c+=(map.containsKey(h)==true)?map.get(h):0;
                    h-=last;
                }
                pw.println(c);
            }
            // pw.println();
        }
    }
 
    static class Pair implements Comparable<Pair>{
        int a;
        int b;
        // int i;
        Pair(int a,int b){
            this.a=a;
 
            this.b=b;
            // this.i=i;
        }   
        public int compareTo(Pair p){
            if(a>p.a)
                return 1;
            if(a==p.a)
                return (b-p.b);
            return -1;
        }
    }
 
    static boolean isPrime(int n) { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        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 long gcd(long a, long b) { 
        if (b == 0) 
            return a; 
        return gcd(b, a % b);  
    } 
    static long fast_pow(long base,long n,long M){
        if(n==0)
           return 1;
        if(n==1)
        return base;
        long halfn=fast_pow(base,n/2,M);
        if(n%2==0)
            return ( halfn * halfn ) % M;
        else
            return ( ( ( halfn * halfn ) % M ) * base ) % M;
    }
    static long modInverse(long n,long M){
        return fast_pow(n,M-2,M);
    }
 
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}