Educational Codeforces Round 81 B. Infinite Prefixes

B. Infinite Prefixes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given string ss of length nn consisting of 0-s and 1-s. You build an infinite string tt as a concatenation of an infinite number of strings ss, or t=ssss…t=ssss… For example, if s=s= 10010, then t=t= 100101001010010...

Calculate the number of prefixes of tt with balance equal to xx. The balance of some string qq is equal to cnt0,q−cnt1,qcnt0,q−cnt1,q, where cnt0,qcnt0,q is the number of occurrences of 0 in qq, and cnt1,qcnt1,q is the number of occurrences of 1 in qq. 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 TT (1≤T≤1001≤T≤100) — the number of test cases.

Next 2T2T lines contain descriptions of test cases — two lines per test case. The first line contains two integers nn and xx (1≤n≤1051≤n≤105, −109≤x≤109−109≤x≤109) — the length of string ss and the desired balance, respectively.

The second line contains the binary string ss (|s|=n|s|=n, si∈{0,1}si∈{0,1}).

It's guaranteed that the total sum of nn doesn't exceed 105105.

Output

Print TT integers — one per test case. For each test case print the number of prefixes or −1−1 if there is an infinite number of such prefixes.

Example

input

Copy

4
6 10
010010
5 3
10101
1 0
0
2 0
01

output

Copy

3
0
1
-1

Note

In the first test case, there are 3 good prefixes of tt: with length 2828, 3030 and 3232.

题目链接：https://codeforces.com/contest/1295/problem/B

题意：

给定一个只含有'0','1' 的字符串，定义一个字符串的q值为'0'字符的个数减去'1'字符的个数

问给定字符串s的所有前缀中（包括空字符串）q值为x的个数。

思路：

分类讨论：

当s的q值为0的时候：

​ 如果s的所有前缀中有出现q值为x的时候，答案是-1

​ 否则为0

当s的q值不为0的时候：

​ 维护出一个周期的q值增量all。

​ 一个周期中到第i个字符的前缀q值为cnt，

​ 当满足$(x - cnt) mod all == 0 $ 且 $ (x - cnt) / all >= 0 $ 答案就加一

可以理解为某个位置的前缀和加上n个周期的贡献为x且贡献次数即之前的周期次数大于等于0次

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int t;
int n;
char s[maxn];
int x;
char key;
// HFUU-QerM
// 17:54:03 

int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);

    t = readint();
    while (t--)
    {
        n = readint(); x = readint();
        if (x >= 0)
        {
            key = '0';
        } else
        {
            x = -x;
            key = '1';
        }
        scanf("%s", s);
        int cnt = 0;
        rep(i, 0, n)
        {
            if (s[i] == key)
            {
                cnt++;
            } else
            {
                cnt--;
            }
        }
        // chu(cnt);
        int ans = 0;
        if (x == 0)
            ans++;
        int all = cnt;
        if (cnt <= 0)
        {
            cnt = 0;
            rep(i, 0, n)
            {
                if (s[i] == key)
                {
                    cnt++;
                } else
                {
                    cnt--;
                }
                if (cnt == x)
                {
                    ans++;
                }
            }
            if (cnt == 0)
            {
                if ((x != 0 && ans > 0) || (ans > 1 && x == 0))
                {
                    printf("-1\n");
                } else
                {
                    printf("0\n");
                }
            } else
            {
                printf("%d\n", ans );
            }
        } else
        {
            cnt = 0;
            rep(i, 0, n )
            {
                if (s[i] == key)
                {
                    cnt++;
                } else
                {
                    cnt--;
                }
                if ((x - cnt) % all == 0 && (x - cnt) / all >= 0 )
                {
                    ans++;
                }
            }
            printf("%d\n", ans );
        }
    }

    return 0;
}