#include <bits/stdc++.h>
using namespace std;

#define int long long

const long double PI = 3.14159265359;

const int MOD = 1e9 + 7;

int sum(int n)
{
    return (n * (n + 1)) / 2;
}

void solve()
{
    int n, k;
    cin >> n >> k;
    string str;
    cin >> str;

    int cnt_1 = count(str.begin(), str.end(), '1'), cnt_0 = count(str.begin(), str.end(), '0');

    int mx_1 = min(n, k + cnt_1), mx_0 = min(n, k + cnt_0);

    cout << max(sum(mx_1) + sum(max(cnt_0 - k, 0LL)), sum(mx_0) + sum(max(cnt_1 - k, 0LL))) + 1 << '\n';
}

signed main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("input.txt", "r"))
    {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}