#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("seif.in");
ofstream g("seif.out");

#define ll long long
#define pb push_back
#define mp make_pair
#define sz size
#define x first
#define y second

#define nmax 1005
#define sigma 27
#define inf (1<<29)

string A, B;
int nextA[nmax][sigma], nextB[nmax][sigma];
int K;
int dp[nmax][nmax];
void citeste(){
    f >> K;f.get();
    getline(f, A);
    getline(f, B);
}

void bagaNext(int next[nmax][sigma], string S, int n){
    for(int i='A'-'A'; i<='Z'-'A'; ++i) next[n][i] = n;
    for(int i=n-1; i>=0; --i){
        for(int lit='A'-'A'; lit<='Z'-'A'; ++lit){
            next[i][lit] = next[i+1][lit];
        }
        next[i][ S[i]-'A' ] = i;
    }
}

void aflaSol(int pozA, int pozB, int n, int m){
    if (pozA != -1 && pozB != -1){
        g << A[pozA];
    }

    for(int lit='Z'-'A'; lit>='A'-'A'; --lit){
        int newPozA = nextA[pozA+1][lit];
        int newPozB = nextB[pozB+1][lit];
        if (newPozA == n || newPozB == m) continue;
        if (dp[newPozA][newPozB] >= K){
            --K; aflaSol(newPozA, newPozB, n, m);
            break;
        }
    }
}

void preproces(){
    int n = A.sz(); int m = B.sz();
    bagaNext(nextA, A, n);
    bagaNext(nextB, B, m);
}

void bagaDinamica(int n, int m){
    for(int i=n-1; i>=0; --i){
        for(int j=m-1; j>=0; --j){
            if (A[i] == B[j]){
                dp[i][j] = dp[i+1][j+1] + 1;
            }else dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
        }
    }
}

void rezolva(){
    preproces();
    // am neovoie de dinamica care sa imi zica ca de la dreapta noilor pozitii se afla sau nu un subsir comun de lungimea dorita
    // dp[i][j] = cel mai lung subsir ce incepe la pozitia i, j si se termina cel tarziu pe n, m
    int n = A.sz(); int m = B.sz();
    for(int i=0; i<=n; ++i) for(int j=0; j<=m; ++j) dp[i][j] = 0;

    bagaDinamica(A.sz(), B.sz());
    aflaSol(-1, -1, n, m);
}

int main(){
    int t =0; f >> t;
    for(; t; --t){
        citeste();
        rezolva();
        g << "\n";
    }
    f.close();
    g.close();

    return 0;
}