for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
ans = []
for i in range(k):
c = t = 0
for j in range(i, n, k):
if s[j] == '1':
c += 1
else:
c -= 1
t = min(t, c)
ans += c - t,
print(s.count('1') - max(ans))#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
// int pre[n];
vector<int> pre(n, 0);
for (int i = 0; i < n; i++)
{
if (i == 0)
pre[i] = s[i] - '0';
else
pre[i] += pre[i - 1] + (s[i] - '0');
}
vector<int> sum(n, 0);
for (int i = n - 1; i >= 0; i--)
{
int xr = (s[i] - '0') ^ 1;
if (i + k - 1 < n)
{
xr += pre[i + k - 1] - pre[i];
}
else
{
xr += pre[n - 1] - pre[i];
}
if (i + k < n)
{
xr += sum[i + k];
}
int r = pre[n - 1] - pre[i] + (s[i] - '0');
sum[i] = min(r, xr);
}
int cnt = 1e15;
for (int i = 0; i < n; i++)
{
int s = sum[i];
if (i)
s += pre[i - 1];
cnt = min(cnt, s);
}
cout << cnt << endl;
}
// int i = 0, j = n - 1;
// while (i < n && s[i] == '0')
// i++;
// while (j >= 0 && s[j] == '0')
// j--;
// if (j < i)
// {
// cout << "0" << endl;
// continue;
// }
// int total = 0;
// for (int l = i; l <= j; l++)
// {
// if (s[l] == '1')
// {
// total++;
// }
// }
// vector<int> rem(k + 1, 0);
// for (int l = i; l <= j; l++)
// {
// if (s[l] == '1')
// {
// rem[(l - i) % (k)]++;
// }
// }
// int ans = 1e6;
// cout << total << endl;
// cout << (j - i + 1) / k << endl;
// for (int l = 0; l < k; l++)
// {
// cout << rem[l] << " ";
// ans = min(ans, (j - i + 1) / k - rem[l] + total - rem[l]);
// cout << ans << " ";
// }
// cout << ans << endl;
}
46A - Ball Game | 114A - Cifera |
776A - A Serial Killer | 25B - Phone numbers |
1633C - Kill the Monster | 1611A - Make Even |
1030B - Vasya and Cornfield | 1631A - Min Max Swap |
1296B - Food Buying | 133A - HQ9+ |
1650D - Twist the Permutation | 1209A - Paint the Numbers |
1234A - Equalize Prices Again | 1613A - Long Comparison |
1624B - Make AP | 660B - Seating On Bus |
405A - Gravity Flip | 499B - Lecture |
709A - Juicer | 1358C - Celex Update |
1466B - Last minute enhancements | 450B - Jzzhu and Sequences |
1582C - Grandma Capa Knits a Scarf | 492A - Vanya and Cubes |
217A - Ice Skating | 270A - Fancy Fence |
181A - Series of Crimes | 1638A - Reverse |
1654C - Alice and the Cake | 369A - Valera and Plates |