#include<bits/stdc++.h>
using namespace std;
const int mod1=1000000007,mod2=1000000009,N=1000005,K=1005;
int hs1[N],hs2[N],ht1[N],ht2[N],p1[N],p2[N];char s[N],t[N];
vector<pair<int,int> >b[K],a[K];pair<int,int> val[K];
int n,m,k,T,vis[K<<1];
int qs1(int l,int r){return (hs1[r]-1ll*hs1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;}
int qs2(int l,int r){return (hs2[r]-1ll*hs2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;}
int qt1(int l,int r){return (ht1[r]-1ll*ht1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;}
int qt2(int l,int r){return (ht2[r]-1ll*ht2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;}
void print(int p,int q)
{
	if(p==0)return;
	for(int i=0;i<a[p-1].size();i++)
	{
		int x=0,y=0;
		if(a[p-1][i].first<n)
		{
			x=a[p-1][i].first+1;y=a[p-1][i].second;
			int l=1,r=min(n-x,m-y),pos=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
				else r=mid-1;
			}
			if(a[p][q]==make_pair(x+pos,y+pos))
			{
				val[p]=make_pair(i,1);print(p-1,i);
				return;
			}
		}
		if(a[p-1][i].second<m)
		{
			x=a[p-1][i].first;y=a[p-1][i].second+1;
			int l=1,r=min(n-x,m-y),pos=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
				else r=mid-1;
			}
			if(a[p][q]==make_pair(x+pos,y+pos))
			{
				val[p]=make_pair(i,2);print(p-1,i);
				return;
			}
		}
		if(a[p-1][i].first<n&&a[p-1][i].second<m)
		{
			x=a[p-1][i].first+1;y=a[p-1][i].second+1;
			int l=1,r=min(n-x,m-y),pos=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
				else r=mid-1;
			}
			if(a[p][q]==make_pair(x+pos,y+pos))
			{
				val[p]=make_pair(i,3);print(p-1,i);
				return;
			}
		}
	}
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		cin>>n>>m>>k;cin>>(s+1)>>(t+1);
		p1[0]=p2[0]=1;
		for(int i=1;i<=max(n,m);i++)
		{
			p1[i]=1ll*p1[i-1]*131%mod1;
			p2[i]=1ll*p2[i-1]*131%mod2; 
		}
		for(int i=1;i<=n;i++)
		{
			hs1[i]=(1ll*hs1[i-1]*131%mod1+s[i])%mod1;
			hs2[i]=(1ll*hs2[i-1]*131%mod2+s[i])%mod2;
		}
		for(int i=1;i<=m;i++)
		{
			ht1[i]=(1ll*ht1[i-1]*131%mod1+t[i])%mod1;
			ht2[i]=(1ll*ht2[i-1]*131%mod2+t[i])%mod2;
		}
		for(int i=0;i<=k;i++)a[i].clear(),b[i].clear(),a[i].shrink_to_fit(),b[i].shrink_to_fit();
		b[0].emplace_back(make_pair(0,0));
		int flag=0;
		for(int i=0;i<=k;i++)
		{
			for(int j=0;j<b[i].size();j++)
			{
				int x=b[i][j].first,y=b[i][j].second;
				int l=1,r=min(n-x,m-y),pos=0;
				while(l<=r)
				{
					int mid=(l+r)>>1;
					if(qs1(x+1,x+mid)==qt1(y+1,y+mid)&&qs2(x+1,x+mid)==qt2(y+1,y+mid))pos=mid,l=mid+1;
					else r=mid-1;
				}
				a[i].emplace_back(make_pair(x+pos,y+pos));
			}
			vector<pair<int,int> >tmp;
			for(int j=-k;j<=k;j++)vis[j+k]=0;
			sort(a[i].begin(),a[i].end());
			for(int j=a[i].size()-1;j>=0;j--)
			{
				if(vis[a[i][j].first-a[i][j].second+k])continue;
				vis[a[i][j].first-a[i][j].second+k]=1;
				tmp.emplace_back(a[i][j]);
			}
			swap(tmp,a[i]);
			//cout<<i<<'\n';
			//for(int j=0;j<a[i].size();j++)cout<<a[i][j].first<<' '<<a[i][j].second<<'\n';
			for(int j=0;j<a[i].size();j++)
			{
				if(a[i][j].first==n&&a[i][j].second==m)
				{
					cout<<"YES\n";
					cout<<i<<'\n';flag=1;
					print(i,j);
					int num1=a[0][0].first,num2=a[0][0].second;
					for(int p=1;p<=i;p++)val[p].first=val[p+1].first;
					for(int p=1;p<=i;p++)
					{
						int q=val[p].first,lq=val[p-1].first;
						int now1=a[p][q].first-a[p-1][lq].first,now2=a[p][q].second-a[p-1][lq].second;
						//cout<<p<<' '<<a[p][q].first<<' '<<a[p][q].second<<'\n';
						if(val[p].second==1)cout<<"DELETE "<<num1+1<<'\n',now1--;
						else if(val[p].second==2)cout<<"INSERT "<<num1+1<<' '<<t[a[p-1][lq].second+1]<<'\n',now1++;
						else cout<<"REPLACE "<<num1+1<<' '<<t[a[p-1][lq].second+1]<<'\n';
						num1+=now1;num2+=now2;
						//cout<<p<<' '<<num1<<' '<<num2<<'\n';
					}
					break;
				}
			}
			if(flag==1)break;
			for(int j=0;j<a[i].size();j++)
			{
				if(a[i][j].first<n)b[i+1].emplace_back(make_pair(a[i][j].first+1,a[i][j].second));
				if(a[i][j].second<m)b[i+1].emplace_back(make_pair(a[i][j].first,a[i][j].second+1));
				if(a[i][j].first<n&&a[i][j].second<m)b[i+1].emplace_back(make_pair(a[i][j].first+1,a[i][j].second+1));
			}
		}
		if(flag==0)cout<<"NO\n";
	}
	return 0;
}