# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Hash=pair<int,int>;
constexpr int N=1e6,p1=1e9+7,p2=1e9+9,Base=998244353;
int n,m,K;
char s1[1000010],s2[1000010];
Hash pw[1000010],sum1[1000010],sum2[1000010];
struct Info
{
	int v,x,y;
	Info(){}
	Info(int v,int x,int y):v(v),x(x),y(y){}
	Info &operator+=(const Info &t)
	{
		if(v<t.v) *this=t;
		return *this;
	}
}f[1010][2010];
inline Hash operator+(const Hash &x,const Hash &y){return {(x.first+y.first)%p1,(x.second+y.second)%p2};}
inline Hash operator-(const Hash &x,const Hash &y){return {(x.first-y.first+p1)%p1,(x.second-y.second+p2)%p2};}
inline Hash operator*(const Hash &x,const Hash &y){return {(ll)x.first*y.first%p1,(ll)x.second*y.second%p2};}
inline Hash geths1(int l,int r){return sum1[r]-pw[r-l+1]*sum1[l-1];}
inline Hash geths2(int l,int r){return sum2[r]-pw[r-l+1]*sum2[l-1];}
int calc(int x,int y)
{
	int l=0,r=min(n-x+1,m-y+1),mid;
	while(l<r)
	{
		mid=(l+r+1)/2;
		if(geths1(x,x+mid-1)==geths2(y,y+mid-1)) l=mid;
		else r=mid-1;
	}
	return l;
}
void getans(int k,int x,int y)
{
	printf("YES\n%d\n",k);
	for(;k;k--)
	{
		Info t=f[k][y-x+K];
		int tx=t.x,ty=tx+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]);
		x=tx;y=ty;
	}
}
int main()
{
	int T;
	cin>>T;
	pw[0]={1,1};
	for(int i=1;i<=N;i++) pw[i]=pw[i-1]*Hash{Base,Base};
	while(T--)
	{
		bool ok=0;
		scanf("%d%d%d%s%s",&n,&m,&K,s1+1,s2+1);
		for(int i=1;i<=n;i++) sum1[i]=sum1[i-1]*Hash{Base,Base}+Hash{s1[i],s1[i]};
		for(int i=1;i<=m;i++) sum2[i]=sum2[i-1]*Hash{Base,Base}+Hash{s2[i],s2[i]};
		for(int i=0;i<=K;i++) fill(f[i],f[i]+2*K+1,Info(-1,0,0));
		f[0][K]=Info(calc(1,1),0,0);
		for(int i=0;i<K && !ok;i++)
			for(int j=-K;j<=K;j++)
				if(~f[i][j+K].v)
				{
					int x=f[i][j+K].v,y=x+j;
					if(x==n && y==m)
					{
						ok=1;getans(i,x,y);
						break;
					}
					if(x<n && y<m) f[i+1][j+K]+=Info(x+1+calc(x+2,y+2),i,j);
					if(x<n && j>-K) f[i+1][j-1+K]+=Info(x+1+calc(x+2,y+1),i,j);
					if(y<m && j<K) f[i+1][j+1+K]+=Info(x+calc(x+1,y+2),i,j);
				}
		if(!ok) puts("NO");
	}
	return 0;
}