tlcs

#include <cstdio>
#include <ctime>

const int N = 1024;
int start = 1, lenx, leny, mat[N][N], lenf, lenl;
char vecx[N], vecy[N];
struct {
    char c;
    int x, y;
} word[N], first[N], last[N];

inline int maxim(int a, int b)
{
    return ((a > b) ? (a) : (b));
}

void writestr(int a, int b)
{
    if (mat[a][b]) {
        if (vecx[a] == vecy[b]) {
            word[mat[a][b]].c = vecx[a];
            word[mat[a][b]].x = a;
            word[mat[a][b]].y = b;
            writestr(a - 1, b - 1);
        } else {
            if (mat[a][b] == mat[a][b - 1]) {
                writestr(a, b - 1);
            } else {
                writestr(a - 1, b);
            }
        }
    }
}

inline void optimize()
{
    int i;
    start = 1;
    lenf = lenl = 0;
    while (vecx[start] == vecy[start]) {
        first[++lenf].c = vecx[start];
        first[lenf].x = first[lenf].y = start;
        ++start;
    }
    while (vecx[lenx] == vecy[leny]) {
        last[++lenl].c = vecx[lenx];
        last[lenl].x = lenx;
        last[lenl].y = leny;
        --lenx;
        --leny;
    }
    for (i = start - 1; i <= lenx && i <= leny; ++i) { // si acum .... ->
        mat[start - 1][i] = mat[i][start - 1] = 0;
    } // initializarea pulii
    while (i <= lenx) {
        mat[i][start - 1] = 0;
        ++i;
    } // inainte nu era nevoie ca mereu aveam start = 1 :D
    while (i <= leny) {
        mat[start - 1][i] = 0;
        ++i;
    }
}

inline void process()
{
    int i, j;
    optimize();
    for (i = start; i <= lenx && i <= leny; ++i) {
        if (vecx[i] == vecy[i]) {
            mat[i][i] = mat[i - 1][i - 1] + 1;
        } else {
            mat[i][i] = maxim(mat[i][i - 1], mat[i - 1][i]);
        }
        for (j = i + 1; j <= lenx && j <= leny; ++j) {
            if (vecx[i] == vecy[j]) {
                mat[i][j] = mat[i - 1][j - 1] + 1;
            } else {
                mat[i][j] = maxim(mat[i][j - 1], mat[i - 1][j]);
            } // aici e magia
            if (vecx[j] == vecy[i]) {
                mat[j][i] = mat[j - 1][i - 1] + 1;
            } else {
                mat[j][i] = maxim(mat[j][i - 1], mat[j - 1][i]);
            }
        }
        while (j <= lenx) {
            if (vecx[j] == vecy[i]) {
                mat[j][i] = mat[j - 1][i - 1] + 1;
            } else {
                mat[j][i] = maxim(mat[j][i - 1], mat[j - 1][i]);
            }
            ++j;
        }
        while (j <= leny) {
            if (vecx[i] == vecy[j]) {
                mat[i][j] = mat[i - 1][j - 1] + 1;
            } else {
                mat[i][j] = maxim(mat[i][j - 1], mat[i - 1][j]);
            }
            ++j;
        }
    }
    writestr(lenx, leny);
}

int main()
{
    //freopen("tlcs.in", "rt", stdin);
    clock_t timp = clock();
    int nr, i, j, sum;
    scanf("%d\n", &nr);
    for (i = 1; i <= nr; ++i) {
        if ((((double) (clock() - timp)) / CLOCKS_PER_SEC) < 4.9) {
            scanf("%d %s\n", &lenx, vecx + 1);
            scanf("%d %s\n", &leny, vecy + 1);
            process();
            sum = mat[lenx][leny] + lenf + lenl;
            if (sum > 0) {
                printf("case %d Y\n", i);
                printf("%d\n", sum);
                for (j = 1; j <= lenf; ++j) {
                    printf("%c %d %d\n", first[j].c, first[j].x, first[j].y);
                }
                for (j = 1; j <= mat[lenx][leny]; ++j) {
                    printf("%c %d %d\n", word[j].c, word[j].x, word[j].y);
                }
                for (j = lenl; j >= 1; --j) {
                    printf("%c %d %d\n", last[j].c, last[j].x, last[j].y);
                }
            } else {
                printf("case %d N\n", i);
            }
        } else {
            printf("case %d N\n", i);
        }
    }
    return 0;
}