#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#define FOR(i,m,n) for(int i=m;i<=n;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int T,n,k,tl=0;
int a[17];
bool b[200007];
string s1,s2;
ll ans=0;
set<char>s;
map<char,int>mp;
void check(int sum){
//  cout<<"<";
    set<int>ss;
    FOR(i,1,sum)ss.insert(a[i]);
    FOR(i,0,n-1)b[i]=0;
    FOR(i,0,n-1)if(s1[i]==s2[i]||ss.find(mp[s1[i]])!=ss.end())b[i]=1;
//  cout<<"!!!!!!!";
//  FOR(i,0,2)cout<<b[i]<<" ";
//  cout<<"!!!!!!!";
    int l;
    ll res=0;
    FOR(i,0,n-1){
        if(i==0)l=i;
        else if(b[i]==1&&b[i-1]==0)l=i;

        if(i==n-1&&b[n]==1)res+=(i-l+1)*(i-l+2)/2;//,printf("{%d,%d,%d}",i,l,(i-l+1)*(i-l+2)/2);
        else if(b[i]==1&&b[i+1]==0)res+=(i-l+1)*(i-l+2)/2;//,printf("{%d,%d,%d}",i,l,(i-l+1)*(i-l+2)/2);;
    }
    ans=max(ans,res);
//  cout<<">";
}
void dfs(int loc,int sum){
    if(loc==tl+1){
        check(sum);
        return;
    }
    dfs(loc+1,sum);
    a[sum+1]=loc;
    if(sum<k)dfs(loc+1,sum+1);
}
int main(){
    cin>>T;
    while(T--){
        s.clear();mp.clear();ans=0;tl=0;
        cin>>n>>k>>s1>>s2;
        FOR(i,0,n-1){
            char sr=s1[i];
            if(s.find(sr)==s.end())s.insert(sr),mp[sr]=++tl;
        }
        dfs(1,0);
        cout<<ans<<endl;
    }
    return 0;
}