#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);
			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};
		}
	}
	
	if(!mp.count({n, m})){
		puts("NO");
		return;
	}
	printf("YES\n%d\n", mp[{n, m}].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.);
	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
*/

answer.code: In function ‘void solve()’:
answer.code:103:15: error: ‘x’ was not declared in this scope
  103 |         while(x || y){
      |               ^
answer.code:103:20: error: ‘y’ was not declared in this scope; did you mean ‘yn’?
  103 |         while(x || y){
      |                    ^
      |                    yn
answer.code:104:21: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  104 |                 auto[i, j]=mp[{x, y}];
      |                     ^
answer.code:104:30: error: no match for ‘operator[]’ (operand types are ‘std::map<std::pair<int, int>, std::pair<int, int> >’ and ‘<brace-enclosed initializer list>’)
  104 |                 auto[i, j]=mp[{x, y}];
      |                              ^
In file included from /usr/include/c++/13/map:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_map.h:504:7: note: candidate: ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::pair<int, int> > >; mapped_type = std::pair<int, int>; key_type = std::pair<int, int>]’
  504 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_map.h:504:34: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const std::map<std::pair<int, int>, std::pair<int, int> >::key_type&’ {aka ‘const std::pair<int, int>&’}
  504 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_map.h:524:7: note: candidate: ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](key_type&&) [with _Key = std::pair<int, int>; _Tp = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, std::pair<int, int> > >; mapped_type = std::pair<int, int>; key_type = std::pair<int, int>]’
  524 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_map.h:524:29: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘std::map<std::pair<int, int>, std::pair<int, int> >::key_type&&’ {aka ‘std::pair<int, int>&&’}
  524 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
answer.code:67:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |         scanf("%s%s", s+1, t+1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~