#include<bits/stdc++.h> 
using namespace std;
typedef long long int ll;
#define MOD 1000000007
#define fo(i,k,n) for(i=k;i<=n;i++)
#define endl '\n'
ll trim(string& s){
	bool anyone=false;
	ll fone=-1,lone=-1,allones=0;
	for(ll i=0;i<s.size();i++){
		if(s[i]=='1') {
			anyone=true;
			if(fone==-1) fone=i;
			lone=i;
			allones++;
		}
	}
	if(!anyone){
		s="";
		return 0;
	}
	s = s.substr(fone,lone-fone+1);
	return allones;
}
ll dp[1000005][2];
ll findCost(string& s,ll idx,ll prev){
	if(idx==s.size()) return 0;
	if(dp[idx][prev]>=0) return dp[idx][prev];
	ll ans;
	if(s[idx]=='1'){
		if(prev==1){
			ans=findCost(s,idx+1,1);
		}else{
			ans=min(1+findCost(s,idx+1,0),findCost(s,idx+1,1));
		}
	}else{//s[i]=='0'
		if(prev==1){
			ans=1+findCost(s,idx+1,1);
		}else{
			ans=min(1+findCost(s,idx+1,1),findCost(s,idx+1,0));
		}
	}
	return dp[idx][prev]=ans;
}
void solve(){
	ll i,j,n,k,allones=0,mncost=LLONG_MAX;
	string s;
	cin>>n>>k>>s;
	fo(i,0,n-1) if(s[i]=='1') allones++;
	for(i=0;i<k;i++){
		string t="";
		for(j=i;j<n;j+=k){
			t+=s[j];
		}
		ll myones = trim(t);
		ll mycost = 0;
		memset(dp,-100,sizeof(dp));
		if(t.size()>0) mycost = min(1+findCost(t,1,0),0+findCost(t,1,1));
		mncost = min(mncost, allones-myones + mycost);
	}
	cout<<mncost<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll t;
	cin>>t;
	//t=1;
	while(t--){
		solve();
	}
	return 0;
}