#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
long long g[3][N],c;
long long ans=-2100000000,ans2=-21000000;
long long dp[N][4],f[N];
char s[3][N];
//dp[i][0]表示截止到第i列时选上面一格的最大1-0数量,dp[i][1]表示截止到第i列时选下面一格的最大1-0数量,dp[i][2]表示第i列两格都选的最大1-0数量 
int main(){
	int T;
	cin>>c>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		ans=0;
		ans2=0;
		for(int i=1;i<=n;i++)dp[i][0]=dp[i][1]=dp[i][2]=f[i]=0;
		cin>>(s[1]+1)>>(s[2]+1);
        for(int i=1;i<=2;i++){
	         for(int j=1;j<=n;j++){
	            	if(s[i][j]=='1')g[i][j]=1;
	            	else g[i][j]=-1;
	            	//cout<<g[i][j]<<" ";
				}
				//cout<<endl;      	
		}

		//最大子段和思想 
		for(int i=1;i<=n;i++){
			long long x=g[1][i]+g[2][i];
			if(x==-2)x=-1;
			f[i]=max(f[i-1]+x,x);
			ans=max(f[i],ans);
			//cout<<"f["<<i<<"]="<<f[i]<<" ";
		}
		//cout<<endl;
		//cout<<"dp["<<1<<"][0]="<<dp[1][0]<<" dp["<<1<<"][1]="<<dp[1][1]<<" dp["<<1<<"][2]="<<dp[1][2]<<endl;
		for(int i=1;i<=n;i++){
			dp[i][0]=max(max(dp[i-1][0]+g[1][i],dp[i-1][2]+g[1][i]),g[1][i]); 
			dp[i][1]=max(max(dp[i-1][1]+g[2][i],dp[i-1][2]+g[2][i]),g[2][i]); 
			dp[i][2]=max( max( max(dp[i-1][2]+g[1][i]+g[2][i],dp[i-1][0]+g[1][i]+g[2][i]) , dp[i-1][1]+g[1][i]+g[2][i] ), g[1][i]+g[2][i]);
			ans2=max( max(dp[n][0],max(dp[n][1],dp[n][2]) ) ,ans2);
			//cout<<"dp["<<i<<"][0]="<<dp[i][0]<<" dp["<<i<<"][1]="<<dp[i][1]<<" dp["<<i<<"][2]="<<dp[i][2]<<endl;
		}
		ans=max(ans,ans2-m*2);
		cout<<ans<<endl;
		//m*2原因:若交换一个0和一个1则0的数量加1,1的数量减1,则总体数量就会减2 
	}
	return 0;
}/*0 2
5 2
11110
01001
7 1
1110000
0001111
*/

wa #10,#11,#16,#17,#22