#include <bits/stdc++.h>
using namespace std;

int n, m, t, k;
int d[1005][1005], nxt[1005][1005];
char a[1005], b[1005], sol[1005];
char s[1005];
inline void rec(int L, int L1, int L2, char s[]){
    if(L1 > n || L2 > m) return ;
    if(nxt[L1][L2]){
        if(nxt[L1][L2] == 1) ++L1;
        if(nxt[L1][L2] == 2) ++L2;
        if(nxt[L1][L2] == 3) {
            s[L++] = s[L1];
            ++L2, ++L1;
        }
        rec(L, L1, L2, s);
        return ;
    }
    char aux[5][1005], w[5], ww = 0;
    memset(aux, 0, sizeof(aux));
    int NR = -1;
    if(d[L1 + 1][L2] == d[L1][L2]){
        ++NR; w[NR] = 0;
        strcpy(aux[NR], s);
        rec(L, L1 + 1, L2, aux[NR]);
    }
    if(d[L1][L2 + 1] == d[L1][L2]){
        ++NR; w[NR] = 1;
        strcpy(aux[NR], s);
        rec(L, L1, L2 + 1, aux[NR]);
    }
    if(d[L1 + 1][L2 + 1] == d[L1][L2] - 1){
        ++NR; w[NR] = 2;
        strcpy(aux[NR], s);
        aux[NR][L] = a[L1];
        rec(L + 1, L1 + 1, L2 + 1, aux[NR]);
    }
    strcpy(s, aux[0]);
    for(int i = 1; i <= NR ; ++i)
        if(strcmp(aux[i], s) > 0)
            strcpy(s, aux[i]), ww = w[i];
    nxt[L1][L2] = ww + 1;
}
int main()
{
    freopen("seif.in", "r", stdin);
    freopen("seif.out", "w", stdout);
    scanf("%d", &t);
    while(t--){
        scanf("%d", &k);
        scanf("%s", a + 1);
        scanf("%s", b + 1);
        int L1 = strlen(a + 1), L2 = strlen(b + 1);
        memset(d, 0, sizeof(d));
        memset(nxt, 0, sizeof(nxt));
        for(int i = L1; i >= 1 ; --i){
            for(int j = L2; j >= 1 ; --j){
                if(a[i] == b[j]) d[i][j] = d[i + 1][j + 1] + 1;
                else d[i][j] = max(d[i + 1][j], d[i][j + 1]);
            }
        }
        char Max = 'A';
        for(int i = 1; i <= L1 ; ++i)
            for(int j = 1; j <= L2 ; ++j)
                if(a[i] == b[j] && d[i][j] >= k)
                    if(a[i] > Max) Max = a[i];
        memset(sol, 0, sizeof(sol));
        n = L1; m = L2;
        for(int i = 1; i <= L1 ; ++i){
            for(int j = 1; j <= L2 ; ++j){
                if(a[i] == b[j] && d[i][j] >= k && a[i] == Max){
                    s[0] = a[i];
                    rec(1, i + 1, j + 1, s);
                    if(strcmp(sol, s) < 1) strcpy(sol, s);
                }
            }
        }
        printf("%s\n", sol);

    }
    return 0;
}