#include <bits/stdc++.h>
using namespace std;
class disjointset {
  long long *parent, *cnt, *rank;
  long long sze;

 public:
  disjointset(long long n) {
    rank = new long long[n + 1];
    parent = new long long[n + 1];
    cnt = new long long[n + 1];
    sze = n;
    for (long long i = 1; i <= n; i++) {
      parent[i] = i;
      rank[i] = 1;
      cnt[i] = 1;
    }
  }
  void join(long long a, long long b) {
    a = find(a);
    b = find(b);
    if (a != b) {
      sze--;
    }
    if (rank[a] > rank[b]) {
      parent[b] = a;
      cnt[a] += cnt[b];
    } else if (rank[a] < rank[b]) {
      parent[a] = b;
      cnt[b] += cnt[a];
    } else {
      parent[b] = a;
      cnt[a] += cnt[b];
      rank[a]++;
    }
  }
  long long find(long long a) {
    return a == parent[a] ? a : parent[a] = find(parent[a]);
  }
  bool check(long long a, long long b) { return find(a) == find(b); }
  long long getcnt(long long a) { return cnt[a]; }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    disjointset s1(n);
    string s;
    cin >> s;
    map<long long, vector<long long> > m1;
    for (long long i = 0; i < n; i++) {
      long long indexl = i - k + 1;
      long long indexr = i + k + 1;
      long long indexp = n - i;
      if (indexl >= 1 && s1.find(indexl) != s1.find(i + 1)) {
        cout << "l" << '\n';
        s1.join(indexl, i + 1);
      }
      if (indexr <= n && s1.find(indexr) != s1.find(i + 1)) {
        s1.join(indexr, i + 1);
      }
      if (s1.find(indexp) != s1.find(i + 1)) {
        s1.join(indexp, i + 1);
      }
    }
    for (long long i = 1; i < n + 1; i++) {
      m1[s1.find(i)].push_back(i);
    }
    long long ans = 0;
    for (auto it : m1) {
      vector<long long> tmp(26, 0);
      for (long long i = 0; i < it.second.size(); i++) {
        long long num = s[it.second[i] - 1] - 'a';
        tmp[num]++;
      }
      long long max1 = 0;
      for (long long i = 0; i < 26; i++) {
        max1 = max(max1, tmp[i]);
      }
      ans += it.second.size() - max1;
    }
    cout << ans << '\n';
  }
  return 0;
}
