#include<bits/stdc++.h>
using namespace std;
#define ll long long
int re(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N = 2e6+10;
char s[3][N];
int n,m,f[N];
int cal1(){
	memset(f,0,sizeof f);
	int res=0;
	for(int i=1;i<=n;i++){
		if(s[1][i]==s[2][i]){
			if(s[1][i]=='1')f[i]=f[i-1]+2;
			else f[i]=f[i-1]-1;
		}
		else{
			f[i]=f[i-1];
		}
		res=max(res,f[i]);
		if(f[i]<0)f[i]=0;
	}
	return res;
}
int dp[3][N];
int cal2(){
	memset(dp,128,sizeof dp);
	dp[1][0]=dp[2][0]=-2*m;
	int ans=0;
	for(int i=1;i<=n;i++){
		if(s[1][i]==s[2][i]){
			if(s[1][i]=='1'){
				dp[1][i]=max(dp[2][i-1]+2,dp[1][i-1]+1);
				dp[2][i]=max(dp[2][i-1]+1,dp[1][i-1]+2);
			}
			else{
				dp[1][i]=max(dp[1][i-1]-1,dp[2][i-1]-2);
				dp[2][i]=max(dp[2][i-1]-1,dp[1][i-1]-2);
			}
		}
		else{
			for(int j=1;j<=2;j++){
				if(s[j][i]=='1')dp[j][i]=max(dp[j][i-1]+1,dp[3-j][i-1]);
				else dp[j][i]=max(dp[j][i-1]-1,dp[3-j][i-1]);
			}
		}
		dp[1][i]=max(dp[1][i],-2*m);
		dp[2][i]=max(dp[2][i],-2*m);
		ans=max(max(ans,dp[1][i]),dp[2][i]);
	}
	return ans;
}
int main(){
	int QWQ=re(),T=re();
	while(T--){
		n=re(),m=re();
		for(int i=1;i<=2;i++)cin>>s[i]+1;
		cout<<max(cal1(),cal2())<<"\n";
	}
	return 0;
}