#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;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGludCBsb25nIGxvbmcKCmNvbnN0IGxvbmcgZG91YmxlIFBJID0gMy4xNDE1OTI2NTM1OTsKCmNvbnN0IGludCBNT0QgPSAxZTkgKyA3OwoKaW50IHN1bShpbnQgbikKewogICAgcmV0dXJuIChuICogKG4gKyAxKSkgLyAyOwp9Cgp2b2lkIHNvbHZlKCkKewogICAgaW50IG4sIGs7CiAgICBjaW4gPj4gbiA+PiBrOwogICAgc3RyaW5nIHN0cjsKICAgIGNpbiA+PiBzdHI7CgogICAgaW50IGNudF8xID0gY291bnQoc3RyLmJlZ2luKCksIHN0ci5lbmQoKSwgJzEnKSwgY250XzAgPSBjb3VudChzdHIuYmVnaW4oKSwgc3RyLmVuZCgpLCAnMCcpOwoKICAgIGludCBteF8xID0gbWluKG4sIGsgKyBjbnRfMSksIG14XzAgPSBtaW4obiwgayArIGNudF8wKTsKCiAgICBjb3V0IDw8IG1heChzdW0obXhfMSkgKyBzdW0obWF4KGNudF8wIC0gaywgMExMKSksIHN1bShteF8wKSArIHN1bShtYXgoY250XzEgLSBrLCAwTEwpKSkgKyAxIDw8ICdcbic7Cn0KCnNpZ25lZCBtYWluKHZvaWQpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgY291dC50aWUoMCk7CiAgICBpZiAoZm9wZW4oImlucHV0LnR4dCIsICJyIikpCiAgICB7CiAgICAgICAgZnJlb3BlbigiaW5wdXQudHh0IiwgInIiLCBzdGRpbik7CiAgICAgICAgZnJlb3Blbigib3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKICAgIH0KICAgIGludCB0ID0gMTsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkKICAgIHsKICAgICAgICBzb2x2ZSgpOwogICAgfQogICAgcmV0dXJuIDA7Cn0=