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

const int m = 30;

void testcase(){
	int n,k;
	string s;
	cin >> n >> k >> s;
	
	string t = s;
	sort(t.begin(),t.end());
	
	vector<int> b;
	for(int i = 0; i < n; ){
		int j = i;
		map<int,int> freq;
		int nonzero = 0;
		auto modify = [&](int x, int v){
			nonzero -= freq[x] != 0;
			freq[x] += v;
			nonzero += freq[x] != 0;
		};
		while(true){
			modify(s[j], +1);
			modify(t[j], -1);
			if(nonzero == 0) break;
			j++;
		}
		b.push_back(j-i+1);
		i = j + 1;
	}
	
	while(!b.empty() && b.back() == 1) b.pop_back();
	reverse(b.begin(),b.end());
	while(!b.empty() && b.back() == 1) b.pop_back();
	
	if(b.empty()){
		cout << "0\n";
		return;
	}
	
	int ans = accumulate(b.begin(),b.end(), 0);
	vector<int> tapu;
	int cnt = 0;
	for(int x : b){
		if(x != 1){
			if(cnt) tapu.push_back(cnt);
			cnt = 0;
		}
		else{
			cnt++;
		}
	}
	
	sort(tapu.rbegin(),tapu.rend());
	for(int i = 0; i < min(k-1,(int)tapu.size()); i++){
		ans -= tapu[i];
	}
	
	cout << ans << '\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt = 1;
	cin >> tt;
	while(tt--){
		testcase();
	}
	return (0-0);
}