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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main implements Runnable{
                                           static final long MAX = 464897L;
                        static class InputReader
                        {
                            private InputStream stream;
                            private byte[] buf = new byte[1024];
                            private int curChar;
                            private int numChars;
                            private SpaceCharFilter filter;
                            private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
                            public InputReader(InputStream stream)
                            {
                                this.stream = stream;
                            }
                            public int read()
                            {
                                if (numChars==-1)
                                    throw new InputMismatchException();
                                if (curChar >= numChars)
                                {
                                    curChar = 0;
                                    try
                                    {
                                        numChars = stream.read(buf);
                                    }
                                    catch (IOException e)
                                    {
                                        throw new InputMismatchException();
                                    }
                                    if(numChars <= 0)
                                        return -1;
                                }
                                return buf[curChar++];
                            }
                            public String nextLine()
                            {
                                String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt()
        {
            int c = read();
            while(isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do
            {
                if(c<'0'||c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }
        public long nextLong()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
        public double nextDouble()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.')
            {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.')
            {
                c = read();
                double m = 1;
                while (!isSpaceChar(c))
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
        public String readString()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do
            {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));
            return res.toString();
        }
        public boolean isSpaceChar(int c)
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        public String next()
        {
            return readString();
        }
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
    public static void main(String args[]) throws Exception
    {
        new Thread(null, new Main(),"Main",1<<26).start();
    }
    static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
    static long lcm(long a,long b) {
        return (a*b)/gcd(a,b);
    }
    int maxn = 1000005;
    long MOD = 1000000007;
    long prime = 29;
    static class Node implements Comparable<Node>{
        int destination;
        long weight;
        Node(int destination,long weight){
            this.destination = destination;
            this.weight = weight;
        }
        Node(){
        }
        @Override
        public int compareTo(Node n) {
            return Long.signum(weight - n.weight);
        }
    }
    static ArrayList<Integer> adj[];
    boolean[][] ans = new boolean[205][205];
    public void run()
    {
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
        int t = sc.nextInt();
        while(t-- > 0) {
            int n = sc.nextInt();
            long m = sc.nextLong();
            String s = sc.next();
            long[] prefix = new long[s.length()+1];
            for(int i = 0;i < n;i++) {
                if(s.charAt(i) == '0') {
                    prefix[i+1] = prefix[i] + 1;
                }else {
                    prefix[i+1] = prefix[i] - 1;
                }
            }
            TreeMap<Long,Integer> tmap = new TreeMap();
            for(int i = 1;i <= n;i++) {
                if(tmap.containsKey(prefix[i])) {
                    tmap.put(prefix[i],tmap.get(prefix[i]) + 1);
                }else {
                    tmap.put(prefix[i],1);
                }
            }
            long count = 0;
            long l;
            if(prefix[n]==0)
                l = 0;
            else
                l = Math.max(0, m/prefix[n] - 2*n);
            long r = l + 4*n;
            for(long i = l;i <= r;i++) {
                long curr = prefix[n] * i;
                long tmp = m - curr;
                if(tmap.containsKey(tmp)) {
                    count += tmap.get(tmp);
                }
            }
            if(m == 0) {
                count++;
            }
            if(prefix[n] == 0 && tmap.containsKey(m)) {
                w.println("-1");
            }else {
                w.println(count);
            }
        }
        w.close();
    }
    static int[] val;
    static final int MAXN = 40005;
    static final int level = 18;
    static int[] depth = new int[MAXN];
    static int[][] parent = new int[MAXN][level];
    static int[][] count = new int[205][MAXN];
    static void dfs(int cur, int prev)
    {
        for(int i = 0;i < 205;i++) {
            count[i][cur] = count[i][prev];
        }
        count[val[cur]][cur]++;
        depth[cur] = depth[prev] + 1;
        parent[cur][0] = prev;
        for (int i = 0; i < adj[cur].size(); i++)
        {
            if (adj[cur].get(i) != prev)
                dfs(adj[cur].get(i), cur);
        }
    }
    static void precomputeSparseMatrix(int n)
    {
        for (int i = 1; i < level; i++)
        {
            for (int node = 1; node <= n; node++)
            {
                if (parent[node][i - 1] != -1)
                    parent[node][i] = parent[parent[node][i - 1]][i - 1];
            }
        }
    }
    static int lca(int u, int v)
    {
        if (depth[v] < depth[u])
        {
            u = u + v;
            v = u - v;
            u = u - v;
        }
        int diff = depth[v] - depth[u];
        // Step 1 of the pseudocode
        for (int i = 0; i < level; i++)
            if (((diff >> i) & 1) == 1)
                v = parent[v][i];
        // now depth[u] == depth[v]
        if (u == v)
            return u;
        // Step 2 of the pseudocode
        for (int i = level - 1; i >= 0; i--)
            if (parent[u][i] != parent[v][i])
            {
                u = parent[u][i];
                v = parent[v][i];
            }
        return parent[u][0];
    }
    static long power(long a,long b,long MOD) {
        long ans = 1;
        a = a % MOD;
        while(b != 0) {
            if(b % 2 == 1) {
                ans = (ans * a) % MOD;
            }
            a = (a * a) % MOD;
            b = b/2;
        }
        return ans;
    }
    class Equal implements Comparable<Equal>{
        Character a;
        int b;
        public Equal(char a,int b){
            this.a = a;
            this.b = b;
        }
        @Override
        public int compareTo(Equal an) {
            // TODO Auto-generated method stub
            return this.a.compareTo(an.a);
        }
    }
    class Pair implements Comparable<Pair>{
        long a;
        long b;
        long c;
        Pair(long a,long b,long c){
            this.b = b;
            this.a = a;
            this.c = c;
        }
        public boolean equals(Object o) {
            Pair p = (Pair)o;
            return this.a == p.a && this.b == p.b && this.c == p.c;
        }
        public int hashCode(){
            return Long.hashCode(a)*27 + Long.hashCode(b)*31;
        }
        public int compareTo(Pair p) {
                return Long.compare(this.a,p.a);
        }
    }
    class Pair3 implements Comparable<Pair3>{
        int a;
        int b;
        int c;
        Pair3(int a,int b,int c){
            this.b = b;
            this.a = a;
            this.c = c;
        }
        public boolean equals(Object o) {
            Pair3 p = (Pair3)o;
            return this.a == p.a && this.b == p.b && this.c == p.c;
        }
        public int hashCode(){
            return Long.hashCode(a)*27 + Long.hashCode(b)*31;
        }
        public int compareTo(Pair3 p) {
            return Long.compare(this.b,p.b);
        }
    }
    class Pair2 implements Comparable<Pair2>{
        int a;
        int b;
        int c;
        Pair2(int a,int b,int c){
            this.b = b;
            this.a = a;
            this.c = c;
        }
        public boolean equals(Object o) {
            Pair2 p = (Pair2)o;
            return this.a == p.a && this.b == p.b && this.c == p.c;
        }
        public int hashCode(){
            return Long.hashCode(a)*27 + Long.hashCode(b)*31 + Long.hashCode(c)*3;
        }
        public int compareTo(Pair2 p) {
            return Long.compare(p.a,this.a);
        }
    }
}