#include<bits/stdc++.h>
#define base 1000000007
#define base2 45279
#define ull unsigned long long
#define N 1000005
#define K 1005
using namespace std;

int n,m,k;
int s1[N],s2[N];
ull hash1[N],hash2[N],pw[N];
int dp[K][K<<1],tr[K][K<<1];

ull pre1[N],pre2[N],pw2[N];

bool check(int x,int y,int len){
	if((x+len-1>n)||(y+len-1>m))return 0;
	if(hash1[x+len-1]-hash1[x-1]*pw[len]==hash2[y+len-1]-hash2[y-1]*pw[len])return 1;
	return 0;
}

bool precheck(int x,int y,int len){
	if((x+len-1>n)||(y+len-1>m))return 0;
	if(pre1[x+len-1]-pre1[x-1]*pw2[len]==pre2[y+len-1]-pre2[y-1]*pw2[len])return 1;
	return 0;
}

int sol(int x,int y){
	int l=0,r=N;
	while(l+1<r){
		int mid=l+r>>1;
		if(check(x,x+y,mid)&&precheck(x,x+y,mid))l=mid;
		else r=mid;
	}
	return l;
}

void print(int x,int y){
	if(!x)return;
	int z=tr[x][y];
	print(x-1,z);int id=dp[x-1][z]+z-k;
	if(z==y){
		printf("REPLACE %d ",id+1);cout<<(char)(s2[id+1]-1+'a')<<endl;
	}if(z==y+1){
		printf("DELETE %d\n",id+1);
	}if(z==y-1){
		printf("INSERT %d ",id+1);cout<<(char)(s2[id+1]-1+'a')<<endl;
	}
}
void DP(){
	for(int i=0;i<=k;++i)for(int j=0;j<=(k<<1);++j)dp[i][j]=tr[i][j]=-1;
	dp[0][k]=0;int ans=-1;
	for(int i=0;i<=k;++i){
		for(int j=0;j<=(k<<1);++j){
			if(dp[i][j]==-1)continue;
			dp[i][j]=dp[i][j]+sol(dp[i][j]+1,j-k);
			if((dp[i][j]+1<=n)&&(dp[i+1][j]+1+j-k<=m)&&dp[i+1][j]<dp[i][j]+1){
				dp[i+1][j]=dp[i][j]+1;tr[i+1][j]=j;
			}
			if((j!=(1<<k))&&(dp[i+1][j]+1+j-k<=m)&&dp[i+1][j+1]<dp[i][j]){
				dp[i+1][j+1]=dp[i][j];tr[i+1][j+1]=j;
			}
			if((dp[i][j]+1<=n)&&(j!=0)&&dp[i+1][j-1]<dp[i][j]+1){
				dp[i+1][j-1]=dp[i][j]+1;tr[i+1][j-1]=j;
			}
		}
		if(dp[i][k-n+m]==n){ans=i;break;}
	}
	if(ans==-1){
		printf("NO\n");return;
	}
	printf("YES\n%d\n",ans);
	print(ans,k-n+m);
}

void solve(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i){char c;cin>>c;s1[i]=c-'a'+1;}
	for(int i=1;i<=m;++i){char c;cin>>c;s2[i]=c-'a'+1;}
	for(int i=1;i<=n;++i)hash1[i]=hash1[i-1]*base+s1[i];
	for(int i=1;i<=m;++i)hash2[i]=hash2[i-1]*base+s2[i];
	for(int i=1;i<=n;++i)pre1[i]=pre1[i-1]*base2+s1[i];
	for(int i=1;i<=m;++i)pre2[i]=pre2[i-1]*base2+s2[i];
	if(k<abs(n-m)){printf("NO\n");return;}
	DP();
}
signed main(){
	int T;scanf("%d",&T);
	pw[0]=pw2[0]=1;for(int i=1;i<N;++i)pw[i]=pw[i-1]*base,pw2[i]=pw2[i-1]*base2;
	while(T--)solve();
	return 0;
}