#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 5, K = 1005;
constexpr int base1 = 31, mod1 = 998244353;
constexpr int base2 = 37, mod2 = 1e9 + 7;
int n, m, k;
char s[N], t[N];
int f[K][K * 2];
pair<int, int> g[K][K * 2];
int s1[N], s2[N];
int t1[N], t2[N];
int pw1[N], pw2[N];
int gets1(int l, int r) { return (s1[r] - 1ll * s1[l - 1] * pw1[r - l + 1] % mod1 + mod1) % mod1; }
int gets2(int l, int r) { return (s2[r] - 1ll * s2[l - 1] * pw2[r - l + 1] % mod2 + mod2) % mod2; }
int gett1(int l, int r) { return (t1[r] - 1ll * t1[l - 1] * pw1[r - l + 1] % mod1 + mod1) % mod1; }
int gett2(int l, int r) { return (t2[r] - 1ll * t2[l - 1] * pw2[r - l + 1] % mod2 + mod2) % mod2; }
int get(int I, int J) {
	int l = I - 1, r = min(n, I + m - J);
	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (gets1(I, mid) == gett1(J, mid - I + J) && gets2(I, mid) == gett2(J, mid - I + J)) l = mid;
		else r = mid - 1;
	}
	return l;
}
void trans(int r, int ld, int nd, int lv, int v) {
	if (f[r + 1][nd + k] < v) {
		f[r + 1][nd + k] = v;
		g[r + 1][nd + k] = {ld, lv};
	}
}
void solve() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> t[i];
	}
	if (abs(n - m) > k) {
		cout << "NO" << "\n";
		return;
	}
	for (int i = 1; i <= n; i++) {
		s1[i] = (1ll * s1[i - 1] * base1 + (s[i] - 'a' + 1)) % mod1;
		s2[i] = (1ll * s2[i - 1] * base2 + (s[i] - 'a' + 1)) % mod2;
	}
	for (int i = 1; i <= m; i++) {
		t1[i] = (1ll * t1[i - 1] * base1 + (t[i] - 'a' + 1)) % mod1;
		t2[i] = (1ll * t2[i - 1] * base2 + (t[i] - 'a' + 1)) % mod2;
	}
	memset(f, ~0x3f, sizeof f);
	f[0][0 + k] = get(0, 0);
	for (int r = 0; r < k; r++) {
		for (int d = -k; d <= k; d++) {
			if (f[r][d + k] < 0) continue;
			int i = f[r][d + k], j = i + d;
			if (i < n && j < m) trans(r, d, d, i, get(i + 2, j + 2));
			if (i < n) trans(r, d, d - 1, i, get(i + 2, j + 1));
			if (j < m) trans(r, d, d + 1, i, get(i + 1, j + 2));
		}
	}
	int fir = -1;
	for (int r = 0; r <= k; r++) {
		if (f[r][m - n + k] == n) {
			fir = r;
			break;
		}
	}
	if (fir == -1) {
		cout << "NO" << "\n";
		return;
	}
	vector<array<int, 3>> v;
	v.push_back({n, m, m - n});
	for (int r = fir, d = m - n; r; r--) {
		int i = g[r][d + k].second;
		d = g[r][d + k].first;
		int j = i + d;
		v.push_back({i, j, d});
	}
	cout << "YES" << "\n" << fir << "\n";
	reverse(v.begin(), v.end());
	int pre = 0;
	for (int id = 0; id + 1 < v.size(); id++) {
		auto [i, j, d] = v[id];
		int diff = v[id + 1][2] - d;
		if (diff == -1) cout << "DELETE" << " " << i + 1 + pre << "\n", pre--;
		else if (diff == 0) cout << "REPLACE" << " " << i + 1 + pre << " " << t[j + 1] << "\n";
		else cout << "INSERT" << " " << i + pre + 1 << " " << t[j + 1] << "\n", pre++;
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (int i = pw1[0] = pw2[0] = 1; i < N; i++) {
		pw1[i] = 1ll * pw1[i - 1] * base1 % mod1;
		pw2[i] = 1ll * pw2[i - 1] * base2 % mod2;
	}
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}