#include<bits/stdc++.h>
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
#define pii pair<int,int>
#define mk make_pair
using namespace std;
inline int read(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)) f|=(c=='-'),c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
//	int t=read();
//	while(t--) work();
//}
const int Maxn=1e6+10,mod=1e9+7,base=233,Maxk=1e3+10;
int pw[Maxn];
int hsha[Maxn],hshb[Maxn];
char A[Maxn],B[Maxn];
int lna,lnb,k;
inline void add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline bool check(int id1,int id2,int ln){
    if(!(id1+ln-1<=lna && id2+ln-1<=lnb)) return false;
    int now1,now2;
    now1=hsha[id1+ln-1];add(now1,mod-1ll*hsha[id1-1]*pw[ln]%mod);
    now2=hshb[id2+ln-1];add(now2,mod-1ll*hshb[id2-1]*pw[ln]%mod);
    return now1==now2;
}
int f[Maxk][Maxk<<1],tr[Maxk][Maxk<<1];
inline int getln(int id1,int id2){
    int ans=0,l=1,r=lna;
    while(l<=r){
        int mid;mid=(l+r)>>1;
        if(check(id1,id2,mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
inline void solve(int x,int y){
    if(!x) return;
    int pre=tr[x][y+k];
    solve(x-1,pre);
	int id=f[x-1][pre+k]+pre;
    if(y==pre) printf("REPLACE %d %c\n",id+1,B[id+1]);
    else if(y>pre) printf("INSERT %d %c\n",id+1,B[id+1]);
    else printf("DELETE %d\n",id+1);
}
inline void work(){
    lna=read();lnb=read();k=read();
    scanf("%s%s",A+1,B+1);
    fr(i,1,lna) hsha[i]=1ll*hsha[i-1]*base%mod,add(hsha[i],A[i]-'a');
    fr(i,1,lnb) hshb[i]=1ll*hshb[i-1]*base%mod,add(hshb[i],B[i]-'a');
    fr(i,0,k) fr(j,-k,k) f[i][j+k]=-1;f[0][k]=0;
    int ans=-1;
    if(abs(lna-lnb)>k){puts("NO");return;}
    fr(i,0,k){
        fr(j,-k,k){
            if(f[i][j+k]==-1) continue;
            int now=f[i][j+k];
            f[i][j+k]=now+getln(now+1,now+j+1);
            // cout<<i<<' '<<j<<' '<<f[i][j+k]<<endl;
            if(f[i][j+k]<lna && f[i+1][j+k]<f[i][j+k]){f[i+1][j+k]=f[i][j+k]+1;tr[i+1][j+k]=j;}
            if(j!=k && f[i+1][j+k+1]<f[i][j+k]){f[i+1][j+k+1]=f[i][j+k];tr[i+1][j+k+1]=j;}
            if(j!=-k && f[i][j+k]<lna && f[i+1][j+k-1]<f[i][j+k]){f[i+1][j+k-1]=f[i][j+k]+1;tr[i+1][j+k-1]=j;}
        }
        if(f[i][lnb-lna+k]==lna){ans=i;break;}
    }
    if(ans==-1) puts("NO");
    else writeln(ans),solve(ans,lnb-lna);
}
inline void init(){
    pw[0]=1;
    fr(i,1,1e6) pw[i]=1ll*pw[i-1]*base%mod;
    int t=read();
    while(t--) work();
}
signed main(){
	// freopen("input.in","r",stdin);
	// freopen("output.out","w",stdout);
    init();
    // printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}