#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=1000;
const int P=10, Mod=20070831;

ll pw[N];

struct Hsh{
	ll hsh[N];

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

	il ll que(int l, int r){return (hsh[r]-hsh[l-1]*pw[r-l+1]%Mod+Mod)%Mod;}
} hs, ht;


int n, m, K, f[1005][2005], g[1005][2005];
char s[N], t[N];

int calc(int i, int j){
	int l=0, r=min(n-i, n-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 upd(int i, int j, int s, int typ){
	if(f[i][j]<s){
		f[i][j]=s;
		g[i][j]=typ;
	}
}

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;
	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=calc(s, s+j);
			if(s+d<n) upd(i+1, j-1+Mov, s+d+1, 0);//删除 s(s+d+1)
			if(s+j+d<m) upd(i+1, j+1+Mov, s+d, 1);//在 s(s+d) 后添加字符 
			if(s+d<n && s+j+d<m) upd(i+1, j+Mov, s+d+1, 2);//修改 s(s+d+1)
		}
	}
	map<pii, pii> mp;
	for(int i=1; i<=K; i++){
		for(int j=-K; j<=K; j++) if(f[i][j+Mov]>=0){
			int s=f[i][j+Mov];
			if(!mp.count({s, s+j})) mp[{s, s+j}]={i, j+Mov};
		}
	}
	int x=n, y=m;
	while(x && y && s[x]==t[y]) x--, y--;
	if(!x && !y){
		printf("YES\n0\n");
		return;
	}
	if(!mp.count({x, y})){
		puts("NO");
		return;
	}
	printf("YES\n%d\n", mp[{x, y}].fr);
	while(x || y){
		auto[i, j]=mp[{x, y}];
		if(g[i][j]==0){
			printf("DELETE %d\n", x);
			x--;
		}
		else if(g[i][j]==1){
			printf("INSERT %d %c\n", x+1, t[y]);
			y--;
		}
		else{
			printf("REPLACE %d %c\n", x, t[y]);
			x--; y--;
		}
		while(x && y && s[x]==t[y]) x--, y--;
	}
}

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