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;
}
233A - Perfect Permutation | 1360A - Minimal Square |
467A - George and Accommodation | 893C - Rumor |
227B - Effective Approach | 1534B - Histogram Ugliness |
1611B - Team Composition Programmers and Mathematicians | 110A - Nearly Lucky Number |
1220B - Multiplication Table | 1644A - Doors and Keys |
1644B - Anti-Fibonacci Permutation | 1610A - Anti Light's Cell Guessing |
349B - Color the Fence | 144A - Arrival of the General |
1106A - Lunar New Year and Cross Counting | 58A - Chat room |
230A - Dragons | 200B - Drinks |
13A - Numbers | 129A - Cookies |
1367B - Even Array | 136A - Presents |
1450A - Avoid Trygub | 327A - Flipping Game |
411A - Password Check | 1520C - Not Adjacent Matrix |
1538B - Friends and Candies | 580A - Kefa and First Steps |
1038B - Non-Coprime Partition | 43A - Football |