#include <iostream>
using namespace std;
bool dat[2][2000006];
struct goo {
    signed v;
    unsigned tip;

    friend goo operator+(const goo& lhs, signed vd){
        return {lhs.v+vd, lhs.tip};
    }

    friend ostream& operator<<(ostream& ost, const goo& rhs){
        ost << "goo{v=" << rhs.v << ",tip=" << rhs.tip << '}';
        return ost;
    }
};
goo dp_[3][2000006];
goo* dp[3] = {dp_[0]+1, dp_[1]+1, dp_[2]+1};
void tmain();
int main(){
	// articulation
	unsigned c,t;
	cin >> c >> t;
	for (unsigned i=0;i<t;i++){
		tmain();
	}
}

signed articulation1(unsigned n){
	signed cur{};
	signed mx{};
	for (auto i=0u;i<n;i++){
		auto va = dat[0][i];
		auto vb = dat[1][i];
		signed opx{};
		if (va && vb){ // 0
			opx = 2;
		} else if (!va && !vb) { // 1
			opx = -1;
		}
		
		cur = max(cur+opx, opx);
		mx = max(mx, cur);
	}
	return mx;
}

auto max0(goo lhs, goo rhs){
	if (lhs.v == rhs.v){
		if (lhs.tip <= rhs.tip){
			return lhs;
		}
		return rhs;
	}
	if (lhs.v < rhs.v){
		return rhs;
	}
    return lhs;
}

goo max1(goo lhs, goo rhs){
	if (lhs.v == rhs.v){
		if (lhs.tip <= rhs.tip){
			return {lhs.v, lhs.tip+1};
		}
		return {rhs.v, rhs.tip+1};
	}
	if (lhs.v < rhs.v){
		return {rhs.v, rhs.tip+1};
	}
    return {lhs.v, lhs.tip+1};
}

goo articulation2(unsigned n){
	signed cur{};
	goo mx{};
	signed opt{};
	// dp_0 = max(dp
	for (auto i=0;i<n;i++){
		auto va = dat[0][i];
		auto vb = dat[1][i];
		signed opx{};
		if (va && vb){ // 0
			opx = 2;
		} else if (!va && !vb) { // 1
			opx = -1;
		} else {
			if (va){
				dp[1][i] = max0(dp[1][i-1], dp[2][i-1]);
				dp[0][i] = max0(max1(dp[0][i-1]+1, dp[2][i-1]+1), goo{1, 1});
			} else {
				dp[0][i] = max0(dp[0][i-1], dp[2][i-1]);
				dp[1][i] = max0(max1(dp[1][i-1]+1, dp[2][i-1]+1), goo{1, 1});
			}
            dp[2][i] = max0(dp[0][i-1], max0(dp[1][i-1], dp[2][i-1]));
			goto ALTER;
		}
		dp[1][i] = dp[0][i] = goo{0};
		dp[2][i] = max0(dp[0][i-1]+opx, max0(dp[1][i-1]+opx, max0(dp[2][i-1], goo{opx})));
		ALTER:
		mx = max0(mx, max0(dp[0][i], max0(dp[1][i], dp[2][i])));
	}
	return mx;
}

void tmain(){
	unsigned n,m;
	cin >> n >> m;
	char cx;
	for (unsigned i=0;i<n;i++){
		cin >> cx;
		dat[0][i] = cx != '0';
	}
	for (unsigned i=0;i<n;i++){
		cin >> cx;
		dat[1][i] = cx != '0';
	}
	
	auto a1 = articulation1(n);
	auto a2 = articulation2(n);

    cout << max(a1, a2.v-min((signed)a2.tip, (signed)m)*2) << '\n';
    return;
	
	cout << a1 << ' ' << a2.v << ' ' << a2.tip << '\n';
    for (unsigned i=0;i<n;i++){
        cout << dp[0][i] << ' ';
    }
    cout << '\n';
    for (unsigned i=0;i<n;i++){
        cout << dp[1][i] << ' ';
    }
    cout << '\n';
    for (unsigned i=0;i<n;i++){
        cout << dp[2][i] << ' ';
    }
    cout << '\n';
}

40pts https://www.luogu.com.cn/record/183717178