#include<bits/stdc++.h>
#define il inline
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define pii pair<int, int>
#define fr first
#define sc second
#define ll long long
#define mset(f, z) memset(f, z, sizeof(f))
#define mcpy(f, g) memcpy(f, g, sizeof(g))
using namespace std;
template<typename T=ll>
il T rd(){
	T s=0; bool f=1; char c=getchar();
	while(!isdigit(c)) f^=(c=='-'), c=getchar();
	while(isdigit(c)) s=s*10+c-'0', c=getchar();
	return f? s:-s;
}
template<typename T> il void ckmx(T &x, T y){if(x<y) x=y;}
template<typename T> il void ckmn(T &x, T y){if(y<x) x=y;}
char _begin;

const int N=1e6+5, Mov=1005;
const int P=19260817, M1=998244353, M2=1e9+7;

ll pw1[N], pw2[N];

struct Hsh{
	ll h1[N], h2[N];

	void init(char *f, int len){
		for(int i=1; i<=len; i++){
			h1[i]=(h1[i-1]*P+f[i]-'a'+1)%M1;
			h2[i]=(h2[i-1]*P+f[i]-'a'+1)%M2;
		}
	}

	il pii que(int l, int r){
		return {
			(h1[r]-h1[l-1]*pw1[r-l+1]%M1+M1)%M1,
			(h2[r]-h2[l-1]*pw2[r-l+1]%M2+M2)%M2
		};
	}
} hs, ht;


int n, m, K, f[1005][2010], dt[1005][2010];
pii g[1005][2010];
char s[N], t[N];

int calc(int i, int j){
	int l=0, r=min(n-i, m-j)+1;
	while(r-l>1){
		int mid=(l+r)/2;
		(hs.que(i+1, i+mid)==ht.que(j+1, j+mid)) ? l=mid : r=mid;
	}
	return l;
}

void solve(){
	n=rd(), m=rd(), K=rd();
	scanf("%s%s", s+1, t+1);
	if(abs(n-m)>K){
		puts("NO");
		return;
	}
	hs.init(s, n);
	ht.init(t, m);
	mset(f, ~63);
	f[0][Mov]=0;
	auto upd=[&](int i, int j, int s, int ii, int jj) {if(f[i][j]<s) f[i][j]=s, g[i][j]={ii, jj};};
	for(int i=0; i<=K; i++){
		for(int j=-K; j<=K; j++) if(f[i][j+Mov]>=0){
			int s=f[i][j+Mov];
			int d=dt[i][j+Mov]=calc(s, s+j);
			f[i][j+Mov]+=d, s+=d;
			if(s<n) upd(i+1, j-1+Mov, s+1, i, j+Mov);//删除 s(s+d+1)
			if(s+j<m) upd(i+1, j+1+Mov, s, i, j+Mov);//在 s(s+d) 后添加字符 
			if(s<n && s+j<m) upd(i+1, j+Mov, s+1, i, j+Mov);//修改 s(s+d+1)
		}
	}
	for(int i=0; i<=K; i++) if(f[i][m-n+Mov]==n){
		printf("YES\n%d\n", i);
		int x=i, y=m-n+Mov;
		for(int j=1; j<=i; j++){
			auto [xx, yy]=g[x][y];
			n=f[x][y]-dt[x][y], m=f[x][y]+y-Mov-dt[x][y];
			if(yy>y) printf("DELETE %d\n", n);
			else if(yy<y) printf("INSERT %d %c\n", n+1, t[m]);
			else printf("REPLACE %d %c\n", n, t[m]);
			x=xx, y=yy;
		}
		return;
	}
	puts("NO");
	// printf("YES\n%d\n", mp[{n, m}].fr);
	// while(n || m){
	// 	auto[i, j]=mp[{n, m}];
	// 	if(g[i][j]==0){
	// 		printf("DELETE %d\n", n);
	// 		n--;
	// 	}
	// 	else if(g[i][j]==1){
	// 		printf("INSERT %d %c\n", n+1, t[m]);
	// 		m--;
	// 	}
	// 	else{
	// 		printf("REPLACE %d %c\n", n, t[m]);
	// 		n--; m--;
	// 	}
	// 	while(n && m && s[n]==t[m]) n--, m--;
	// }
}

char _end;
signed main(){
	debug("%lfMB\n", (&_end-&_begin)/1024./1024.);
	pw1[0]=1; for(int i=1; i<=1e6; i++) pw1[i]=pw1[i-1]*P%M1;
	pw2[0]=1; for(int i=1; i<=1e6; i++) pw2[i]=pw2[i-1]*P%M2;
	int T=rd();
	while(T--) solve();
	return 0;
}
/*
1
3 3 100
bbb
abc
*/