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.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.InputMismatchException;

/**
 * @author Mubtasim Shahriar
 */

public class InfinitePre {


	public static void main(String[] args) {

		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader sc = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Solver solver = new Solver();
		int t = sc.nextInt();
//		int t = 1;
		while(t--!=0) {
			solver.solve(sc, out);
		}		
		out.close();

	}

	static class Solver {
		public void solve(InputReader sc, PrintWriter out) {
			int n = sc.nextInt();
			long x = sc.nextLong();
			String s = sc.next();
			long[] sum = new long[n];
			if(s.charAt(0)=='0') sum[0] = 1;
			else sum[0] = -1;
			for(int i = 1; i < n; i++) {
				if(s.charAt(i)=='1') sum[i] = sum[i-1]-1;
				else sum[i] = sum[i-1]+1;
			}
//			out.println(Arrays.toString(sum));
			long ans = 0;
			if(x==0) ans = 1;
			long last = sum[n-1];
			boolean found = false;
			for(int i = 0; i < n; i++) {
				if(last==0) {
					if(sum[i]==x) found = true;
				}
				else if((x-sum[i])%last==0 && (x-sum[i])/last>=0) {
					found = true;;
					ans++;
				}
			}
			if(found) {
				if(last!=0) out.println(ans);
				else out.println(-1);
			} else {
				if(x==0) out.println(1);
				else out.println(0);
			}
		}
	}

	static class InputReader { 
		private boolean finished = false;

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		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 int peek() {
			if (numChars == -1) {
				return -1;
			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					return -1;
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar];
		}

		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 String nextString() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				if (Character.isValidCodePoint(c)) {
					res.appendCodePoint(c);
				}
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null) {
				return filter.isSpaceChar(c);
			}
			return isWhitespace(c);
		}

		public static boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private String readLine0() {
			StringBuilder buf = new StringBuilder();
			int c = read();
			while (c != '\n' && c != -1) {
				if (c != '\r') {
					buf.appendCodePoint(c);
				}
				c = read();
			}
			return buf.toString();
		}

		public String readLine() {
			String s = readLine0();
			while (s.trim().length() == 0) {
				s = readLine0();
			}
			return s;
		}

		public String readLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines) {
				return readLine();
			} else {
				return readLine0();
			}
		}

		public BigInteger readBigInteger() {
			try {
				return new BigInteger(nextString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}

		public char nextCharacter() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			return (char) c;
		}

		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 boolean isExhausted() {
			int value;
			while (isSpaceChar(value = peek()) && value != -1) {
				read();
			}
			return value == -1;
		}

		public String next() {
			return nextString();
		}

		public SpaceCharFilter getFilter() {
			return filter;
		}

		public void setFilter(SpaceCharFilter filter) {
			this.filter = filter;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
		public int[] nextIntArray(int n){
			int[] array=new int[n];
			for(int i=0;i<n;++i)array[i]=nextInt();
			return array;
		}
		public int[] nextSortedIntArray(int n){
			int array[]=nextIntArray(n);
			Arrays.sort(array);
			return array;
		}
		public int[] nextSumIntArray(int n){
			int[] array=new int[n];
			array[0]=nextInt();
			for(int i=1;i<n;++i)array[i]=array[i-1]+nextInt();
			return array;
		}
		public long[] nextLongArray(int n){
			long[] array=new long[n];
			for(int i=0;i<n;++i)array[i]=nextLong();
			return array;
		}
		public long[] nextSumLongArray(int n){
			long[] array=new long[n];
			array[0]=nextInt();
			for(int i=1;i<n;++i)array[i]=array[i-1]+nextInt();
			return array;
		}
		public long[] nextSortedLongArray(int n){
			long array[]=nextLongArray(n);
			Arrays.sort(array);
			return array;
		}
	}


}