把两个错的拼起来去最大值就对了

#include <bits/stdc++.h>

void Freopen() {
    freopen("", "r", stdin);
    freopen("", "w", stdout);
}

using namespace std;
const int N = 2e6 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;

int n, m;

int col[N][3];

struct node {
	int f, g;
	
	node operator + ( const node rhs) const {
		return {f + rhs.f, g + rhs.g};
	}
} dp[N][3];

node mg( node a, node b) {
	if (a.f > b.f) return a;
	if (a.f < b.f) return b;
	
	return a.g > b.g ? a : b;
}

char s[N];

void solve() {
	cin >> n >> m;
			
	cin >> (s + 1);
	
	for ( int i = 1; i <= n; i ++)
		col[i][1] = s[i] - '0';
	
	cin >> (s + 1);
		
	for ( int i = 1; i <= n; i ++)
		col[i][2] = s[i] - '0';
	
		
	for ( int i = 1; i <= n; i ++) {
		if (col[i][1] == 1 && col[i][2] == 1) {
			dp[i][0] = dp[i][1] = {1, 0}, dp[i][2] = {2, 0};
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + dp[i][0], dp[i - 1][2] + dp[i][0]));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + dp[i][1], dp[i - 1][2] + dp[i][1]));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		} else if (col[i][1]) {
			dp[i][0] = {1, 1}, dp[i][1] = {-1, 0}, dp[i][2] = {0, 0};
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + (dp[i - 1][0].g < m ? dp[i][0] : (node){1, 1}), dp[i - 1][2] + (dp[i - 1][2].g < m ? dp[i][0] : (node){1, 1})));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + dp[i][1], dp[i - 1][2] + dp[i][1]));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		} else if (col[i][2]) {
			dp[i][0] = {-1, 0}, dp[i][1] = {1, 1}, dp[i][2] = {0, 0};
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + dp[i][0], dp[i - 1][2] + dp[i][0]));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + (dp[i - 1][1].g < m ? dp[i][1] : (node){1, 1}), dp[i - 1][2] + (dp[i - 1][2].g < m ? dp[i][1] : (node){1, 1})));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		} else {
			dp[i][0] = dp[i][1] = {-1, 0}, dp[i][2] = {-2, 0};	
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + dp[i][0], dp[i - 1][2] + dp[i][0]));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + dp[i][1], dp[i - 1][2] + dp[i][1]));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		}
	}
	
	int ans = 0;
	
	for ( int i = 1; i <= n; i ++)
		ans = max(ans, max(dp[i][0].f - min(m, dp[i][0].g) * 2, max(dp[i][1].f - min(m, dp[i][1].g) * 2, dp[i][2].f - min(m, dp[i][2].g) * 2)));
		
	for ( int i = 1; i <= n; i ++) {
		if (col[i][1] == 1 && col[i][2] == 1) {
			dp[i][0] = dp[i][1] = {1, 0}, dp[i][2] = {2, 0};
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + dp[i][0], dp[i - 1][2] + dp[i][0]));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + dp[i][1], dp[i - 1][2] + dp[i][1]));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		} else if (col[i][1]) {
			dp[i][0] = {-1, 1}, dp[i][1] = {-1, 0}, dp[i][2] = {0, 0};
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + (dp[i - 1][0].g < m ? dp[i][0] : (node){1, 1}), dp[i - 1][2] + (dp[i - 1][2].g < m ? dp[i][0] : (node){1, 1})));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + dp[i][1], dp[i - 1][2] + dp[i][1]));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		} else if (col[i][2]) {
			dp[i][0] = {-1, 0}, dp[i][1] = {-1, 1}, dp[i][2] = {0, 0};
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + dp[i][0], dp[i - 1][2] + dp[i][0]));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + (dp[i - 1][1].g < m ? dp[i][1] : (node){1, 1}), dp[i - 1][2] + (dp[i - 1][2].g < m ? dp[i][1] : (node){1, 1})));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		} else {
			dp[i][0] = dp[i][1] = {-1, 0}, dp[i][2] = {-2, 0};	
			
			dp[i][0] = mg(dp[i][0], mg(dp[i - 1][0] + dp[i][0], dp[i - 1][2] + dp[i][0]));
			dp[i][1] = mg(dp[i][1], mg(dp[i - 1][1] + dp[i][1], dp[i - 1][2] + dp[i][1]));
			dp[i][2] = mg(dp[i][2], mg(dp[i - 1][0] + dp[i][2], mg(dp[i - 1][1] + dp[i][2], dp[i - 1][2] + dp[i][2])));
		}
	}
	
	for ( int i = 1; i <= n; i ++)
		ans = max(ans, max(dp[i][0].f, max(dp[i][1].f, dp[i][2].f)));

	cout << ans << '\n';
}

signed main() {
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int c, t;
	
	for (cin >> c >> t; t; t --) solve();
}