#include <set>
#include <map>
#include <list>
#include <queue>
#include <cmath>
#include <time.h>
#include <random>
#include <bitset>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <iomanip>
#include <assert.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mk make_pair
#define fi first
#define se second
inline int read(){
int t = 0,f = 1;
register char c = getchar();
while (c < 48 || c > 57) f = (c == '-') ? -1 : 1,c = getchar();
while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
return f * t;
}
inline int reads(char *s){
int t = 0;
register char c = getchar();
while (c < 'a' || c > 'z') c = getchar();
while (c >= 'a' && c <= 'z') s[++t] = c,c = getchar();
return t;
}
const int N = 1e6 + 10,K = 1000 + 10,P = 131;
int T,n,m,k,dp[K][K << 1],x0,y0;
char s[N],t[N];
ull shsh[N],thsh[N],pw[N];
pair <int,int> fr[K][K << 1];
inline void chkmn(int &x,int v) {if (v < x) x = v;}
inline ull chash(ull *hs,int l,int r){
return hs[r] - hs[l] * pw[r - l];
}
void upd(int x,int y,int kk,int xx,int yy){
if (x > n || y > m) return ;
int l = 0,r = min(n - x,m - y);
if (r && s[x + 1] != t[y + 1]) r = 0;
while (l < r){
int mid = (l + r + 1) >> 1;
if (!mid || chash(shsh,x + 1,x + mid) == chash(thsh,y + 1,y + mid)) l = mid;
else r = mid - 1;
}
x += l,y += l;
int i = kk,j = x - y + k;
if (x > dp[i][j]){
if (xx == -1) x0 = i,y0 = j;
dp[i][j] = x,fr[i][j] = mk(xx,yy);
}
}
int cnt = 0;
void out(int x,int y){
if (x == x0 && y == y0) return ;
int xx = fr[x][y].fi,yy = fr[x][y].se;
out(xx,yy);
int i = dp[x][y],j = i - (y - k);
int ii = dp[xx][yy],jj = ii - (yy - k);
if (y == yy){
printf("REPLACE %d %c\n",cnt + ii + 1,t[jj + 1]);
}
if (y == yy - 1){
printf("INSERT %d %c\n",cnt + ii + 1,t[jj + 1]);
++cnt;
}
if (y == yy + 1){
printf("DELETE %d\n",cnt + ii + 1);
--cnt;
}
}
void solve(){
cnt = 0;
n = read(),m = read(),k = read();
reads(s),reads(t);
pw[0] = 1;
for (int i = 1;i <= max(n,m);i++) pw[i] = pw[i - 1] * P;
auto ghash = [&](ull *hs,char *s,int n){
for (int i = 1;i <= n;i++) hs[i] = hs[i - 1] * P + s[i] - 'a' + 1;
};
ghash(shsh,s,n),ghash(thsh,t,m);
for (int i = 0;i <= n;i++) for (int j = 0;j <= (k << 1);j++) dp[i][j] = -1;
// dp[0][k] = 0;
upd(0,0,0,-1,-1);
for (int i = 0;i <= k;i++){
for (int j = 0;j <= (k << 1);j++){
int x = dp[i][j],y = x - (j - k);
if (x < 0 || y < 0) continue;
upd(x + 1,y + 1,i + 1,i,j);
upd(x,y + 1,i + 1,i,j);
upd(x + 1,y,i + 1,i,j);
}
}
int j = n - m + k;
bool f = 0;
for (int i = 0;i <= k;i++) f |= (dp[i][j] == n);
if (!f) {puts("NO");return ;}
puts("YES");
for (int i = 0;i <= k;i++){
if (dp[i][j] == n){
printf("%d\n",i);
out(i,j);
return ;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
#endif
T = read();
while (T--) solve();
return 0;
}