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.*;
import java.util.*;

public class Main implements Runnable {
    static boolean use_n_tests = true;
    static int stack_size = 1 << 27;
    static long mod = 1_000_000_007;

    void solve(FastScanner in, PrintWriter out, int testNumber) {
        int n, x;
        n = in.nextInt();
        x = in.nextInt();
        char[] s = in.next().toCharArray();
        Map<Integer, Integer> balances = new HashMap<>();
        int b = 0;
        int cnt0 = 0;
        int cnt1 = 0;
        int mn = Integer.MAX_VALUE;
        int mx = Integer.MIN_VALUE;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '0') {
                cnt0++;
            } else {
                cnt1++;
            }
            balances.merge(cnt0 - cnt1, 1, Integer::sum);
            mn = Math.min(mn, cnt0 - cnt1);
            mx = Math.max(mx, cnt0 - cnt1);
        }
        b = cnt0 - cnt1;
//        if (b != 0 && x == 0) {
//            out.println(1);
//            return;
//        }
        int ans = 0;
        if (x == 0) {
            ans = 1;
        }
        if (b == 0 && balances.containsKey(x)) {
            out.println(-1);
        } else {
            if (b == 0 && !balances.containsKey(x)) {
                out.println(ans);
            } else {
                int dist = 0;
                if (x < mn) {
                    if (b < 0) {
                        dist = (mn - x) / -b;
                        if ((mn - x) % -b != 0) {
                            dist++;
                        }
                    } else {
                        out.println(ans);
                        return;
                    }
                    x += dist * -b;
                } else if (x > mx) {
                    if (b > 0) {
                        dist = (x - mx) / b;
                        if ((x - mx) % b != 0) {
                            dist++;
                        }
                    } else {
                        out.println(ans);
                        return;
                    }
                    x -= dist * b;
                }

                while (x <= mx && x >= mn) {
                    ans += balances.get(x);
                    x -= b;
                }
                out.println(ans);
            }
        }

    }

    // ****************************** template code ***********

    static class Range {
        int l, r;
        int id;

        public int getL() {
            return l;
        }

        public int getR() {
            return r;
        }

        public Range(int l, int r, int id) {
            this.l = l;
            this.r = r;
            this.id = id;
        }
    }

    static class Array {
        static Range[] readRanges(int n, FastScanner in) {
            Range[] result = new Range[n];
            for (int i = 0; i < n; i++) {
                result[i] = new Range(in.nextInt(), in.nextInt(), i);
            }
            return result;
        }

        static public Integer[] read(int n, FastScanner in) {
            Integer[] out = new Integer[n];
            for (int i = 0; i < out.length; i++) {
                out[i] = in.nextInt();
            }
            return out;
        }

        static public int[] readint(int n, FastScanner in) {
            int[] out = new int[n];
            for (int i = 0; i < out.length; i++) {
                out[i] = in.nextInt();
            }
            return out;
        }
    }

    class Graph {
        List<List<Integer>> create(int n) {
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                graph.add(new ArrayList<>());
            }
            return graph;
        }
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream io) {
            br = new BufferedReader(new InputStreamReader(io));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

    void run_t_tests() {
        int t = in.nextInt();
        int i = 0;
        while (t-- > 0) {
            solve(in, out, i++);
        }
    }

    void run_one() {
        solve(in, out, -1);
    }

    @Override
    public void run() {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);
        if (use_n_tests) {
            run_t_tests();
        } else {
            run_one();
        }
        out.close();
    }

    static FastScanner in;
    static PrintWriter out;

    public static void main(String[] args) throws InterruptedException {
        Thread thread = new Thread(null, new Main(), "", stack_size);
        thread.start();
        thread.join();
    }
}