#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define endl '\n'
#define ilihg ios_base::sync_with_stdio(false);cin.tie(NULL)

void rec(vector<vector<int>> &v,int i,int n,int l,int k,vector<int> &r){
	if(i==n){
		if(l<=k){
			v.push_back(r);
		}
		return;
	}
	r.push_back(i);
	rec(v,i+1,n,l+1,k,r);
	r.pop_back();
	rec(v,i+1,n,l,k,r);
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	clock_t time_req=clock();
	ilihg;
	//
	int t=1;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string a,z;
        cin>>a>>z;
        set<char> s;
        for(int i=0;i<n;i++){
        	s.insert(a[i]);
        }
        vector<int> c;
        for(auto u:s){
        	c.push_back(u-97);
        }
        vector<int> b(26);
        vector<int> r;
        vector<vector<int>> v;
        rec(v,0,c.size(),0,k,r);
        ll ans=0;
        for(auto u:v){
        	ll f=0;
        	for(auto g:u){
        		b[c[g]]=1;
        	}
        	ll p=0;
        	for(int i=0;i<n;i++){
        		if(a[i]==z[i]||b[a[i]-97]){

        		}
        		else{
        			f+=(i-p)*(i-p+1)/2;
        			p=i+1;
        		}
        	}
        	f+=(n-p)*(n-p+1)/2;
        	ans=max(ans,f);
        	for(auto g:u){
        		b[c[g]]=0;
        	}
        }
        cout<<ans<<endl;
    }
#ifndef ONLINE_JUDGE
    cout<<"Time : "<<fixed<<setprecision(6)<<((double)(clock()-time_req))/CLOCKS_PER_SEC<<endl;
#endif    
}