#include <bits/stdc++.h>

#define readFile freopen("in.txt","r",stdin)
#define writeFile freopen("out.txt","w",stdout)
#define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 100010;

int dp[N], tree[4*N], alt[N];
int n,k;
string s;

void update(int node, int l, int r, int idx, int val){
    if(l==r){
        tree[node] = val;
        return;
    }
    int mid = (l+r)>>1;
    if(idx<=mid) update(node<<1,l,mid,idx,val);
    else update(node<<1|1,mid+1,r,idx,val);
    tree[node] = min(tree[node<<1],tree[node<<1|1]);
}

int query(int node, int l, int r, int ll, int rr){
    if(l > rr || r < ll) return 1e9;
    if(l>=ll&&r<=rr) return tree[node];
    int mid = (l+r)>>1;
    return min(query(node<<1,l,mid,ll,rr),query(node<<1|1,mid+1,r,ll,rr));
}

void init(){
    memset(dp,0,sizeof dp);
    memset(alt,0,sizeof alt);
    for(int i = 0; i < 4*N; i++) tree[i] = 1e9;
    for(int i = 3; i <= n+1; i++) alt[i] = alt[i-1] + (bool)(s[i]!=s[i-1]);
}

int main(){
#ifndef ONLINE_JUDGE
    readFile;
#endif
    fastIO;
    int t; cin >> t;
    while(t--){
        cin >> n >> k >> s;
        s = "$$" + s;
        init();
        update(1,1,N,1,0);
        for(int i = 2; i <= n+1; i++){
            dp[i] = dp[i-1] + 1;
            int l = max(i-k,1), r = i-1;
            int e = alt[r+1]-alt[l]+1;
            if((r-l+1)>e){
                int q = query(1,1,N,l-1,r-1);
                dp[i] = min(dp[i],q+1);
            }
            update(1,1,N,i,dp[i]);
        }
        cout << dp[n+1]-1 << "\n";
    }
    return 0;
}