include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

include

include <bits/stdc++.h>

using namespace __gnu_pbds; using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t; cin >> t; while (t--) { ll n, k; cin >> n >> k; string a, b; cin >> a >> b; vector < ll > mp(26, 0), mp1(26, 0); vector < vector < ll >> calc(26, vector < ll > (n + 1, 0)); vector < ll > pre(n + 1, 0); ll len = 0; ll ans = 0; if (a[0] == b[0]) { pre[0] = 1; len++; } calc[a[0] — 'a'][0] = 1; mp1[a[0] — 'a']++; for (ll i = 1; i < n; i++) { calc[a[i] — 'a'][i]++; if (a[i] == b[i]) { len++; pre[i] += (len + pre[i — 1]); } else if (a[i] != b[i]) { pre[i] = pre[i — 1]; len = 0; } } for (ll i = 0; i < 26; i++) { for (ll j = 1; j < n; j++) { calc[i][j] += calc[i][j — 1]; } } if (k == 0) { cout << pre[n — 1] << endl; continue; } ll i = 0; ll j = 0; set < char > s1; len = 0;

ll count = 0;
while (j < n) {
  mp[a[j] - 'a'] = j;
  if (a[j] != b[j]) {
    s1.insert(a[j]);
  }
  ll now = s1.size();
  if (now > k) {
    while (a[i] == b[i]) {
      i++;
    }
    s1.erase(a[i]);
    i = mp[a[i] - 'a'] + 1;
    now--;
  }
  len = j - i + 1;
  if (i == 0) {
    ll count = 0;
    for (auto x: s1) {
      count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j]);
    }
    ans = max(ans, pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);
  } else {
    ll count = 0;
    for (auto x: s1) {
      count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j] + calc[x - 'a'][i - 1]);
    }
    ans = max(ans, pre[i - 1] + pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);
  }
  j++;
}
cout << ans << endl;

} }