C

#include <bits/stdc++.h>
using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define pb     push_back
#define ppb    pop_back


int main()
{
    _test
    {
        int n, k;
        string s;
        cin>>n>>k>>s;

        vector<int> cnt0(k);
        vector<int> cnt1(k);

        for(int i=1; i<=n; i++)
        {
            if(s[i-1] == '0')       cnt0[i%k]++;
            if(s[i-1] == '1')       cnt1[i%k]++;
        }

        ll int ans1 = 0;
        ll int ans0 = 0;

        for(int i=0; i<k; i++)
        {
            ans0 += (cnt1[i])/2 + 2*(cnt1[i]%2);
            ans1 += cnt0[i];

            if(cnt1[i]==0 && cnt0[i]!=0)     ans1 = 1e12;

            assert((cnt0[i] + cnt1[i]) >= 2);
        }

        cout<<min(ans0, ans1)<<"\n";
    }
}