#include <bits/stdc++.h>
namespace // my guiding star
{
#define filein(x) freopen(x".in", "r", stdin);
#define fileout(x) freopen(x, "w", stdout);
#define fileerr(x) freopen(x, "w", stderr);
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define files(x) freopen(x".in", "r", stdin), freopen(x".ans", "w", stdout);
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned u32;
template <typename T>
using pr = pair<T, T>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd; 
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}
const int N = 1e6 + 233, P1 = 1e9 + 7, P2 = 1e9 + 9, base = 131, K = 1005;
int n, m, k;
string s1, s2;
struct hash_t
{
	int first, second;
	inline hash_t operator + (const hash_t& rhs) const {return {(first + rhs.first) % P1, (second + rhs.second) % P2};}
	inline hash_t operator - (const hash_t& rhs) const {return {((first - rhs.first) % P1 + P1) % P1, ((second - rhs.second) % P2 + P2) % P2};}
	inline hash_t operator * (const hash_t& rhs){return {(int)(1ll * first * rhs.first % P1), (int)(1ll * second * rhs.second % P2)};}
	inline bool operator == (const hash_t& rhs) const {return (first == rhs.first) && (second == rhs.second);}
}pw[N], hsh1[N], hsh2[N];
inline hash_t hash1(int l, int r){return hsh1[r] - pw[r-l+1] * hsh1[l-1];}
inline hash_t hash2(int l, int r){return hsh2[r] - pw[r-l+1] * hsh2[l-1];}
struct info
{
	int v, x, y;
	info& operator += (const info& rhs){return (v < rhs.v) ? *this = rhs : *this;}
}dp[K][K << 1];
inline int lcp(int x, int y)
{
	int l = 0, r = min(n-x+1, m-y+1);
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (hash1(x, x+mid-1) == hash2(y, y+mid-1)) l = mid + 1;
		else r = mid - 1;
	}
	return l - 1;
}
void print(int p, int x, int y)
{
	printf("YES\n%d\n", p);
	while (p)
	{
		info t = dp[p][y-x+k];
		int tx = t.x, ty = t.y;
		if (y - x == ty - tx) printf("REPLACE %d %c\n", tx+1, s2[ty+1]);
		else if (y - x == ty - tx - 1) printf("DELETE %d\n", tx+1);
		else printf("INSERT %d %c\n", tx+1, s2[ty+1]);
		--p; x = tx; y = ty;
	}
}
int main()
{
	int T; scanf("%d", &T); pw[0] = {1, 1};
	for (int i=1; i<N; i++) pw[i] = pw[i-1] * hash_t{base, base};
	while (T--)
	{
		scanf("%d%d%d", &n, &m, &k);
		cin >> s1 >> s2; s1 = "$" + s1; s2 = "$" + s2;
		for (int i=1; i<=n; i++) hsh1[i] = hsh1[i-1] * hash_t{base, base} + hash_t{s1[i], s1[i]};
		for (int i=1; i<=m; i++) hsh2[i] = hsh2[i-1] * hash_t{base, base} + hash_t{s2[i], s2[i]};
		for (int i=0; i<=k; i++) fill(dp[i], dp[i]+2*k+1, info{-1, 0, 0});
		bool ok = false; dp[0][k] = {lcp(1, 1), 0, 0};
		for (int i=0; (i<=k)&&!ok; i++)
			for (int j=-k; j<=k; j++)
			{
				if (!~dp[i][j+k].v) continue;
				int x = dp[i][j+k].v, y = x + j;
				if ((x == n) && (y == m)){ok = true; print(i, x, y); break;}
				if ((i < k) && (x < n) && (y < m)) dp[i+1][j+k] += info{x+1+lcp(x+2,y+2), x, y};
				if ((i < k) && (x < n) && (j > -k)) dp[i+1][j-1+k] += info{x+1+lcp(x+2,y+1), x, y};
				if ((i < k) && (y < m) && (j < k)) dp[i+1][j+1+k] += info{x+lcp(x+1,y+2), x, y};
			}
		if (!ok) puts("NO");
	}
	return 0;
}