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.ByteArrayInputStream;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.PrintWriter;
    import java.util.*;
    import java.io.*;
    import java.math.*;
    public class Main {
        InputStream is;
        PrintWriter out;
        String INPUT = "";
        //class  Declaration

        static class pair implements Comparable < pair > {
            long x;
            long y;


            pair(long i, long j) {
                x = i;
                y = j;


            }
            public int compareTo(pair p) {
                if (this.x != p.x) {
                    return Long.compare(this.x,p.x);
                } else {
                    return Long.compare(this.y,p.y);
                }
            }
            public int hashCode() {
                return (x + " " + y).hashCode();
            }
            public String toString() {
                return x + " " + y;
            }
            public boolean equals(Object o) {
                pair x = (pair) o;
                return (x.x == this.x && x.y == this.y);
            }
        }
        // int[] dx = {0,0,1,-1};
        // int[] dy = {1,-1,0,0};
        // int[] ddx = {0,0,1,-1,1,-1,1,-1}; 
        // int[] ddy = {1,-1,0,0,1,-1,-1,1};

    int inf = (int) 1e9 + 9;
    long biginf  = (long)1e17 + 7 ;
    long mod =  (int)1e9 + 7;  
   

    void solve() throws Exception {
       int t=ni();
        while(t-->0){
            int n=ni(),x=ni();
            char[] str =ns().toCharArray();
            long[] bal = new long[n];
            long cnt0=0,cnt1=0;
            long present = 0;
            for(int i=0;i<n;++i){
                if(str[i]=='0') cnt0++;
                if(str[i]=='1') cnt1++;
                bal[i] = cnt0 - cnt1;
            
                if(bal[i]==x) present++;


            }
            if( bal[n-1]==0 && present>0 ){
                pn(-1);
            }
            else{
                if(bal[n-1]!=0){
                long diff = bal[n-1];
                for(int i=0;i<n;++i){
                    if((x - bal[i])%diff == 0 && ((x-bal[i])/diff) > 0) present++;

                }
                }
                if(x==0) present++;

                pn(present);
            }

        }

    //    pn((5/(-4)));
        
        
    }
 


        long pow(long a, long b) {
            long result = 1;
            while (b > 0) {
                if (b % 2 == 1) result = (result * a) % mod;
                b /= 2;
                a = (a * a) % mod;
            }
            return result;
        }


        void print(Object o) {
            System.out.println(o);
            System.out.flush();
        }



        long gcd(long a, long b) {
            if (b == 0)
                return a;
            return gcd(b, a % b);
        }
        void run() throws Exception {
            is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
            out = new PrintWriter(System.out);

            long s = System.currentTimeMillis();
            solve();
            out.flush();
            if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");
        }


        public static void main(String[] args) throws Exception {
            new Main().run();
        }

        //output methods
        private void pn(Object o) {
            out.println(o);
        }
        private void p(Object o) {
            out.print(o);
        }
        private ArrayList < ArrayList < Integer >> ng(int n, int e) {
            ArrayList < ArrayList < Integer >> g = new ArrayList < > ();
            for (int i = 0; i <= n; ++i) g.add(new ArrayList < > ());

            for (int i = 0; i < e; ++i) {
                int u = ni(), v = ni();
                g.get(u).add(v);
                g.get(v).add(u);
            }

            return g;
        }

        private ArrayList < ArrayList < pair >> nwg(int n, int e) {
            ArrayList < ArrayList < pair >> g = new ArrayList < > ();
            for (int i = 0; i <= n; ++i) g.add(new ArrayList < > ());

            for (int i = 0; i < e; ++i) {
                int u = ni(), v = ni(), w = ni();
                g.get(u).add(new pair(w, v));
                g.get(v).add(new pair(w, u));
            }

            return g;
        }


        //input methods
        private byte[] inbuf = new byte[1024];
        public int lenbuf = 0, ptrbuf = 0;


        private int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }




        private boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        private int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        private double nd() {
            return Double.parseDouble(ns());
        }
        private char nc() {
            return (char) skip();
        }

        private String ns() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        private char[] ns(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        private char[][] nm(int n, int m) {
            char[][] map = new char[n][];
            for (int i = 0; i < n; i++) map[i] = ns(m);
            return map;
        }

        private int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

        private int ni() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        private long nl() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        private void tr(Object...o) {
            if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
        }
        void watch(Object...a) throws Exception {
            int i = 1;
            print("watch starts :");
            for (Object o: a) {
                //print(o);
                boolean notfound = true;
                if (o.getClass().isArray()) {

                    String type = o.getClass().getName().toString();
                    //print("type is "+type);
                    switch (type) {
                        case "[I":
                            {
                                int[] test = (int[]) o;
                                print(i + " " + Arrays.toString(test));
                                break;
                            }
                        case "[[I":
                            {
                                int[][] obj = (int[][]) o;

                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[J":
                            {

                                long[] obj = (long[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[J":
                            {

                                long[][] obj = (long[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[D":
                            {

                                double[] obj = (double[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[D":
                            {

                                double[][] obj = (double[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[Ljava.lang.String":
                            {

                                String[] obj = (String[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[Ljava.lang.String":
                            {

                                String[][] obj = (String[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[C":
                            {
                                char[] obj = (char[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[C":
                            {

                                char[][] obj = (char[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }



                        default:
                            {
                                print(i + " type not identified");
                                break;
                            }
                    }
                    notfound = false;

                }
                if (o.getClass() == ArrayList.class) {
                    print(i + " al: " + o);
                    notfound = false;
                }
                if (o.getClass() == HashSet.class) {
                    print(i + " hs: " + o);
                    notfound = false;
                }
                if (o.getClass() == TreeSet.class) {
                    print(i + " ts: " + o);
                    notfound = false;
                }
                if (o.getClass() == TreeMap.class) {
                    print(i + " tm: " + o);
                    notfound = false;
                }
                if (o.getClass() == HashMap.class) {
                    print(i + " hm: " + o);
                    notfound = false;
                }
                if (o.getClass() == LinkedList.class) {
                    print(i + " ll: " + o);
                    notfound = false;
                }
                if (o.getClass() == PriorityQueue.class) {
                    print(i + " pq : " + o);
                    notfound = false;
                }
                if (o.getClass() == pair.class) {
                    print(i + " pq : " + o);
                    notfound = false;
                }

                if (notfound) {
                    print(i + " unknown: " + o);
                }
                i++;
            }
            print("watch ends ");
        }

    }