#include <bits/stdc++.h>
using namespace std;
namespace Slongod{
const int N = 1e6+7 , M = 1005 , mod1 = 998244353 , mod2 = 1e9+7 , inf = 0x3f3f3f3f;

namespace hash
{
    int seed1 , seed2 , pw1[N] , pw2[N]; mt19937 rd(time(nullptr));
    inline void inithash()
    {
        seed1 = uniform_int_distribution<>(1,100)(rd);
        seed2 = uniform_int_distribution<>(1,100)(rd);
        pw1[0] = 1; for (int i = 1; i < N; i++){pw1[i] = 1ll * pw1[i-1] * seed1 % mod1;}
        pw2[0] = 1; for (int i = 1; i < N; i++){pw2[i] = 1ll * pw2[i-1] * seed2 % mod2;}
    }
    inline void makehash(const int n , const char s[] , pair<int,int> hash[])
    {
        hash[0] = {0 , 0};
        for (int i = 1; i <= n; i++) {
            hash[i].first = (1ll * hash[i-1].first * seed1 + s[i]) % mod1;
            hash[i].second = (1ll * hash[i-1].second * seed2 + s[i]) % mod2;
        }
    }
    inline pair<int,int> gethash(int l , int r , pair<int,int> hash[])
    {
        int res1 = (hash[r].first - 1ll * hash[l-1].first * pw1[r - l + 1] % mod1 + mod1) % mod1;
        int res2 = (hash[r].second - 1ll * hash[l-1].second * pw2[r - l + 1] % mod2 + mod2) % mod2;
        return {res1 , res2};
    }
}

int T , n , m , k , *rk[M] , *fa[M];
char s[N] , t[N];
pair<int,int> hs[N] , ht[N];
inline int lcp(int x , int y)
{
    int l = 0 , r = min(n - x + 1 , m - y + 1) , res = 0;
    while(l <= r) {
        int mid = (r - l) / 2 + l;
        if (hash::gethash(x , x + mid - 1 , hs) == hash::gethash(y , y + mid - 1 , ht)) {
            res = mid; l = mid + 1;
        } else {
            r = mid - 1;
        }
    } return res;
}
int output(int dep , int j)
{
    if (dep == 0){return 0;}
    int delta = output(dep - 1 , fa[dep][j]);
    int x = rk[dep][j] , y = x - j;
    int tx = rk[dep-1][fa[dep][j]] , ty = tx - fa[dep][j];
    if (x - tx > y - ty) {
        cout << "DELETE " << tx + 1 + delta << '\n';
        return delta - 1;
    }
    if (y - ty > x - tx) {
        cout << "INSERT " << tx + 1 + delta << ' ' << t[ty + 1] << '\n';
        return delta + 1;
    }
    cout << "REPLACE " << tx + 1 + delta << ' ' << t[ty + 1] << '\n';
    return delta;
}
void main()
{
    for (int i = 0; i < M; i++) {
        rk[i] = new int[M*2]; rk[i] += M;
        fa[i] = new int[M*2]; fa[i] += M;
    } hash::inithash();

    bool flag = false;
    for (cin >> T , flag = T < 10; T; T--) {
        //Input and Inithash/DP
        cin >> n >> m >> k >> (s + 1) >> (t + 1);
        if (k == 0 and T == 100){flag = true;}
        hash::makehash(n , s , hs); hash::makehash(m , t , ht);
        for (int i = 0; i <= k; i++) {
            for (int j = -k; j <= k; j++) {
                rk[i][j] = -inf; fa[i][j] = 0;
            }
        }

        //DongPlan
        rk[0][0] = lcp(1 , 1);
        for (int i = 0; i <= k; i++) {
            for (int j = -k , x , y , tmp; j <= k; j++) {
                if (rk[i][j] != -inf) {
                    x = rk[i][j]; y = rk[i][j] - j;
                    //S 走一步
                    if (x < n) {
                        tmp = lcp(x + 2 , y + 1);
                        if (x + 1 + tmp > rk[i+1][j+1]) {
                            rk[i+1][j+1] = x + 1 + tmp;
                            fa[i+1][j+1] = j;
                        }
                    }
                    //T 走一步
                    if (y < m) {
                        tmp = lcp(x + 1 , y + 2);
                        if (x + tmp > rk[i+1][j-1]) {
                            rk[i+1][j-1] = x + tmp;
                            fa[i+1][j-1] = j;
                        }
                    }
                    //同时走一步
                    if (x < n and y < m) {
                        tmp = lcp(x + 2 , y + 2);
                        if (x + 1 + tmp > rk[i+1][j]) {
                            rk[i+1][j] = x + 1 + tmp;
                            fa[i+1][j] = j;
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int i = 0; i <= k; i++) {
            if (rk[i][n-m] == n) {
                ans = i; break;
            }
        }
        if (flag or T == 83) {
            if (ans == -1){cout << "NO\n";}
            else{cout << "YES\n" << ans << '\n'; output(ans , n - m);}
        }
    }
}
}int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    return Slongod :: main(),0;
}