#include<bits/stdc++.h>
#define ll long long 
#define f(i,n) for(int i=0;i<n;i++) 
#define fr(i,a,b) for(int i=a;i<b;i++) 
#define F first 
#define S second 
#define mp make_pair 
#define pb push_back 

using namespace std;

int fun(vector<int> a) 
{ 

	int size = a.size();
    f(i,size)if(a[i]==0)a[i]=-1;
	int max_so_far = INT_MIN, max_ending_here = 0, 
       start =0, end = 0, s=0; 
  
    for (int i=0; i< size; i++ ) 
    { 
        max_ending_here += a[i]; 
  
        if (max_so_far < max_ending_here) 
        { 
            max_so_far = max_ending_here; 
            start = s; 
            end = i; 
        } 
  
        if (max_ending_here < 0) 
        { 
            max_ending_here = 0; 
            s = i + 1; 
        } 
    } 
    if(max_so_far>0){
    	int sum = 0;
    	f(i,size){
    		if(i>=start and i<=end){
    			if(a[i]==-1)sum++;
			}else{
				if(a[i]==1)sum++;
			}
		}
		return sum;
	}else
		return 0; 
} 



void test(){
	ll n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	
	int total = 0;
	f(i,n){
		total = total + (s[i]-'0');
	}
	ll ans = n;
	int index = -1;
	for(int i=k-1;i>=0;i--){
		vector<int> v;
		int temp=0;
		for(int j=n-(k-i);j>=0;j=j-k){
			v.pb(s[j]-'0');
			temp = temp + (s[j]-'0');
		}
		ll cal = total-temp;
		cal = cal + fun(v);
		ans = min(ans,cal);
	}
		
	cout<<ans<<"\n";
}

int main(){ 
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	cin>>t;
	while(t--){
		test();
	}
}