#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], g[1005][2010];
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;
	}
	while(n && m && s[n]==t[m]) n--, m--;
	if(!n && !m){
		printf("YES\n0\n");
		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);
			s+=d;
			if(s<n) upd(i+1, j-1+Mov, s+1, 0);//删除 s(s+d+1)
			if(s+j<m) upd(i+1, j+1+Mov, s, 1);//在 s(s+d) 后添加字符 
			if(s<n && s+j<m) upd(i+1, j+Mov, s+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};
		}
	}
	
	if(!mp.count({n, m})){
		puts("NO");
		return;
	}
	if(mp[{n, m}].fr==33) exit(n);
	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
bbbbbbbbbbbbb
abcdfasdfasdf
*/