#include <bits/stdc++.h>

using namespace std;

ifstream fin("seif.in");
ofstream fout("seif.out");

const int NMAX = 1005;
char a[NMAX],b[NMAX];
int dp[NMAX][NMAX],rasp[NMAX];
int dp_1[30][NMAX],dp_2[30][NMAX];

void solve(){
    memset(dp,0,sizeof(dp));
    memset(dp_1,0,sizeof(dp_1));
    memset(dp_2,0,sizeof(dp_2));
    int k;
    fin >> k;
    fin >> (a+1) >> (b+1);
    int n=strlen(a+1),m=strlen(b+1);
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;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]);
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<=26;j++) dp_1[j][i]=dp_1[j][i+1];
        dp_1[a[i]-'A'][i]=i;
    }
    for(int i=m;i>=1;i--){
        for(int j=0;j<=26;j++) dp_2[j][i]=dp_2[j][i+1];
        dp_2[b[i]-'A'][i]=i;
    }
    int dim=dp[1][1];
    int poz1=1,poz2=1,fixate=1;
    for(int i=1;i<=dim;i++){
        for(int j='Z'-'A';j>='A'-'A';j--){
            int poz_j_sirul_1=dp_1[j][poz1];
            int poz_j_sirul_2=dp_2[j][poz2];
            if(poz_j_sirul_1==0 or poz_j_sirul_2==0) continue;
            if(dp[poz_j_sirul_1+1][poz_j_sirul_2+1]>=k-fixate){
                rasp[fixate++]=j;
                poz1=poz_j_sirul_1+1;
                poz2=poz_j_sirul_2+1;
                break;
            }
        }
    }
    for(int i=1;i<=fixate-1;i++) fout << (char)(rasp[i]+'A');
    fout << '\n';
}

int main()
{
    int T;
    fin >> T;
    for(int t=1;t<=T;t++){
        solve();
    }
    return 0;
}