#include <bits/stdc++.h>
using namespace std;
using uint64 = unsigned long long;
void Solve() {
    int n, m, k; cin >> n >> m >> k;
    string s, t; cin >> s >> t;
    if(abs(n - m) > k) return puts("NO"), void();
    vector<uint64> hshs(n + 1), hsht(m + 1);
    vector<uint64> pw(max(n, m) + 1); pw[0] = 1;
    const int B = 137; const uint64 Mod = 1e17l + 7;
    const auto Hsh = [&](const vector<uint64> &h, int p, int q)
        { return (h[p + q] + (__uint128_t)(Mod - h[p]) * pw[q]) % Mod; };
    for(int i = 0; i < max(n, m); ++i) pw[i + 1] = pw[i] * B % Mod;
    for(int i = 0; i < n; ++i) hshs[i + 1] = (hshs[i] * B + s[i] - 'a') % Mod;
    for(int i = 0; i < m; ++i) hsht[i + 1] = (hsht[i] * B + t[i] - 'a') % Mod;
    const auto &match = [&](int x, int ofs) {
        const int y = x + ofs; int A = x;
        if(x > n || y > m) return 0;
        for(int L = x + 1, R = n; L <= R; ) {
            const int M = (L + R) >> 1, e = M - x;
            const uint64 u = Hsh(hshs, x, e), v = Hsh(hsht, y, e);
            if(u == v) L = M + 1, A = M; else R = M - 1;
        }
        return A;
    };
    using pii = pair<int, int>; vector<vector<pii>> f;
    f.emplace_back(1, pii(match(0, 0), 0));
    const auto &Cmax = [](pii &x, pii y) { x = max(x, y); };
    const auto &check = [&](int p) {
        if(f[p][m - n + p].first != n) return 0;
        printf("YES\n%d\n", p);
        for(int w = m - n; p > 0; --p) {
            const int V = f[p][w + p].second;
            const int u = V >> 2, v = u + 1, ofs = V & 3;
            switch(ofs) {
                case 0: printf("DELETE %d\n", v), ++w; break;
                case 1: printf("REPLACE %d %c\n", v, t[u + w]); break;
                case 2: printf("INSERT %d %c\n", v, t[u + --w]); break;
            }
        }
        return 1;
    };
    for(int p = 0, q = 1;; ++p, ++q) {
        if(abs(n - m) <= p && check(p)) return;
        if(p == k) return puts("NO"), void();
        f.emplace_back(q << 1 | 1, pii(0, 0));
        for(int i = 0; i <= p * 2; ++i) {
            const int s = f[p][i].first, t = s << 2;
            Cmax(f[q][i + 0], {match(s + 1, i - q), t | 0});
            Cmax(f[q][i + 1], {match(s + 1, i - p), t | 1});
            Cmax(f[q][i + 2], {match(s, i - p + 1), t | 2});
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T; cin >> T; while(T--) Solve();
}