#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define cmx(x,y) x = max(x,y)
#define cmn(x,y) x = min(x,y)
#define ary(k) array<int,k>
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef uint64_t ull;
struct H{
	ull x; H(ull x=0) : x(x) {}
	H operator+(H o) { return x + o.x + (x+o.x < x);}
	H operator-(H o) { return *this + ~o.x; }
	H operator*(H o) { auto m = (__uint128_t)x * o.x;
		return H((ull)m)+(ull)(m >> 64); }
	ull get() const { return x + !~x; }
	bool operator==(H o) const { return get() == o.get(); }
	bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11+3;
struct HashInterval{
	vector<H> ha,pw;
	HashInterval(string& str) : ha(sz(str)+1),pw(ha) {
		pw[0] = 1;
		rep(i,0,sz(str))
			ha[i+1] = ha[i]*C+str[i],pw[i+1] = pw[i]*C;
	}
	H hashInterval(int a, int b){
		return ha[b]-ha[a]*pw[b-a];
	}
};
int dp[2006][2006];
pii from[2006][2006];
/*
int longest(string &sa, string &sb, int a, int b) {
    int res = 0;
    while (sa+res < sz(sa) && sb+res < sz(sb) && sa[a+res] == sb[b+res]) {
        res++;
    }
    return res;
}*/

void fun() {
    int n, m, k;
    cin >> n >> m >> k;
    string sa, sb;
    cin >> sa >> sb;
	HashInterval ha(sa),hb(sb);
	auto longest = [&](int a, int b){
		int lena = n-a,lenb = m-b;	
		auto chk = [&](int l){
			if(l == 0) return true;
			auto x = ha.hashInterval(a,a+l),y = hb.hashInterval(b,b+l);
			return x == y;
		};
		int lo = 0, hi = min(lena,lenb);
		while(lo < hi){
			int mid = (lo+hi+1)/2;
			if(chk(mid)) lo = mid;
			else hi = mid-1;
		}
		return lo;
	};
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= 2*k+2; j++) {
            dp[i][j] = -1000000001;
        }
    }
    dp[0][k+1] = 0;
    for (int i = 0; i <= k; i++) {
        for (int d = 1; d <= 2*k+1; d++) {
            int a = dp[i][d], b = a + d - k - 1;
            if (a < 0 || b < 0)
                continue;
            dp[i][d] += longest(a, b);
            if (dp[i+1][d] < dp[i][d] + 1) {
                from[i+1][d] = {i, d};
                dp[i+1][d] = dp[i][d] + 1;
            }
            if (dp[i+1][d+1] < dp[i][d]) {
                from[i+1][d+1] = {i, d};
                dp[i+1][d+1] = dp[i][d];
            }
            if (dp[i+1][d-1] < dp[i][d] + 1) {
                from[i+1][d-1] = {i, d};
                dp[i+1][d-1] = dp[i][d] + 1;
            }
        }
    }
    pair<int, int> best = {1000000, 0};
    for (int i = 0; i <= k; i++) {
        for (int d = 0; d <= 2*k+2; d++) {
            int a = dp[i][d], b = a + d - k - 1;
            if (a == n && b == m) {
                best = min(best, {i, d});
            }
//            cerr << i << " " << d << " " << a << " " << b << " " << dp[i][d] << "\n";
        }
    }
    if (best.FS == 1000000) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    cout << best.FS << "\n";
    while (best.FS > 0) {
        auto [i, d] = best;
        int dell = false;
        if (from[i][d].SD == d+1) {
            cout << "DELETE ";
            dell = true;
        } else if (from[i][d].SD == d - 1) {
            cout << "INSERT ";
        } else {
            cout << "REPLACE ";
        }
        best = from[i][d];
        i = best.FS, d = best.SD;
        int a = dp[i][d], b = a + d - k - 1;
        cout << a+1;
        if (!dell) {
            cout << " " << sb[b];
        }
        cout << "\n";
    }
}

signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    int z;
    cin >> z;
    while (z--) fun();
}