#include <bits/stdc++.h>
using namespace std;
#define ll int
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int main() {
	vector<vector<bool>> DP0(2501, vector<bool>(2501, false));
	vector<vector<ll>> DP1(2501, vector<ll>(5001, -1));
	vector<ll> BPS(2501,0);
	vector<ll> QPS(2501,0);
	ll T; cin >> T;
	for(int t = 0; t < T; t++) {
		ll N, M; cin >> N >> M;
		string H,P;
		cin >> H;
		cin >> P;
		ll B0=0, Q0=0;
		for(int i = 0; i < N; i++) {
			if(H[i] == 'B') B0++;
			else if(H[i] == 'Q') Q0++;
		}

		BPS.assign(M,0);
		QPS.assign(M,0);
		for(int j = 0; j < M; j++) {
			if(P[j] == 'B') BPS[j+1]++;
			else if(P[j] == 'Q') QPS[j+1]++;
			BPS[j+1] += BPS[j]; QPS[j+1] += QPS[j];
		}
		auto query = [&](ll K) {
			//cout << "QUERYING " << K << "\n\n";
			
			for(int i = 0; i <= M; i++) DP0[i].assign(K+1, false);
			for(int i = 0; i <= M; i++) DP1[i].assign(M+N+1,-1);

			DP0[0][0] = true;
			for(int i = 1; i <= M; i++) {
				for(int b = 0; (b <= K) && (2*b <= i); b++) {
					// (i-1,b) -> (i, b)
					{
						ll qthen = QPS[i-1] + Q0;
						ll qspent = i-1 - 2*b;
						if((qthen - qspent > 0) && DP0[i-1][b]) DP0[i][b] = true;
					}

					// (i-2, b-1) -> (i,b)
					if(i-2>=0 && b-1>=0) {
						ll bthen = BPS[i-2] + B0;
						ll bspent = b-1;
						if((bthen - bspent)>0 && DP0[i-2][b-1]) DP0[i][b] = true;
					}

					//cout << i << " " << b << " " << DP0[i][b] << endl;

					if(DP0[i][b] && i == M) return true;

					ll bnow = BPS[i]+B0-b;
					if(bnow > 0 && i+2 >= M && DP0[i][b]) return true;

					if(DP0[i][b] && b == K) {
						// handsize is full, transition to second-state.
						ll qnow = QPS[i] + Q0;
						ll qspent = i - 2*b;
						ll bnow = BPS[i]+B0-b;
						DP1[i][bnow] = max(DP1[i][bnow], qnow-qspent);
					}

					
				}
			}

			//cout << "GOTO DP2\n";

			if(K == 0) DP1[0][B0] = Q0;

			for(int i = 1; i <= M; i++) {
				for(int b = 0; b <= N+M; b++) {
					// we are at full hand-size.

					//cout << i << " " << b << " " << DP1[i][b] << endl;
					// played a Q to get here.
					{
						ll bthen = b;
						if(P[i-1] == 'B') bthen--;
						ll cost = -1;
						if(P[i-1] == 'Q') cost = 0;
						if(bthen >= 0 && DP1[i-1][bthen]>0) {
							DP1[i][b] = max(DP1[i][b], DP1[i-1][bthen]+cost);
						}
					}

					//cout << i << " " << b << " " << DP1[i][b] << endl;


					// played a B to get here.
					if(i-2 >= 0) {
						//cout << P[i-2] << " ";
						ll bthen = b+1;
						if(P[i-2] == 'B') bthen--;
						ll cost = 0;
						if(P[i-2] == 'Q') cost++;
						//cout << bthen << " ";
						if(bthen > 0 && bthen <= N+M && DP1[i-2][bthen]>=0) {
							DP1[i][b] = max(DP1[i][b], DP1[i-2][bthen]+cost);
						}
					}

					//cout << i << " " << b << " " << DP1[i][b] << endl;
					if(i+2 >= M && b > 0 && DP1[i][b] >= 0) return true;
					if(DP1[i][b]>=0 && i==M) return true;
				}
			}

			//cout << "Failed.\n";

			return false;
		};

		if(!query(M)) {
			cout << "IMPOSSIBLE\n"; continue;
		}

		ll kl = 0;
		ll kh = M;
		while(kl < kh) {
			ll km = (kl+kh)/2;
			if(query(km)) kh = km;
			else kl = km+1;
		}

		cout << kh+N << endl;


	}
}