#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int typ,T,n,m,dp[N][N][2][2],a[3][N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cin>>typ>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=2;i++){
            for(int j=1;j<=n;j++){
                char c;
                cin>>c,c-='0';
                if(!c){
                    a[i][j]=-1;
                }
                else{
                    a[i][j]=1;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                for(int A=0;A<2;A++){
                    for(int B=0;B<2;B++){
                        dp[i][j][A][B]=-1e9;
                    }
                }
            }
        }
        //dp[i][j][A][B]为我们从第1列到第i列选一个联通块 且这个联通块对于第i列的状态是(A,B) 而且交换了j列 此时的最大收益
        for(int i=0;i<2;i++){
            dp[1][i][0][0]=0,dp[1][i][1][1]=a[1][1]+a[2][1];
            if(i){
                dp[1][i][1][0]=a[2][1],dp[1][i][0][1]=a[1][1];
            }
            else{
                dp[1][i][1][0]=a[1][1],dp[1][i][0][1]=a[2][1];
            }
        }
        for(int i=2;i<=n;i++){
            for(int j=0;j<=min(i,m);j++){
                for(int A=0;A<2;A++){
                    for(int B=0;B<2;B++){
                        if(A||B){
                            int x=1e9,y=1e9;
                            if(A&&B){
                                x=a[1][i]+a[2][i]+max(0,max(dp[i-1][j][0][1],max(dp[i-1][j][1][0],dp[i-1][j][1][1])));
                                if(j){
                                    y=a[1][i]+a[2][i]+max(0,max(dp[i-1][j-1][0][1],max(dp[i-1][j-1][1][0],dp[i-1][j-1][1][1])));
                                }
                            }
                            else{
                                int tmp;
                                if(A){
                                    tmp=a[1][i];
                                }
                                else{
                                    tmp=a[2][i];
                                }
                                x=tmp+max(0,max(dp[i-1][j][A][B],dp[i-1][j][1][1]));
                                if(!A){
                                    tmp=a[1][i];
                                }
                                else{
                                    tmp=a[2][i];
                                }
                                if(j){
                                    y=tmp+max(0,max(dp[i-1][j-1][A][B],dp[i-1][j-1][1][1]));
                                }
                            }
                            dp[i][j][A][B]=min(x,y);
                        }
                    }
                }
            }
        }
        int ans=-1e9;
        for(int i=1;i<=n;i++){
            for(int A=0;A<2;A++){
                for(int B=0;B<2;B++){
                    int tmp=1e9;
                    for(int j=0;j<=min(i,m);j++){
                        tmp=min(tmp,dp[i][j][A][B]);
                    }
                    ans=max(ans,tmp);
                }
            }
        }
        cout<<ans<<'\n';
    }
}