#include<fstream>
#include<cstring>
#include<string>

using namespace std;

const char iname[]="seif.in";
const char oname[]="seif.out";
const int maxn=1005;

ifstream f(iname);
ofstream g(oname);

int n,m,i,j,t,k,a[maxn][maxn],nxt1[maxn][26],nxt2[maxn][26],p;
char A[maxn],B[maxn];

int main()
{
    f>>t;
    while(t--)
    {
        f>>k;
        f.get();
        f>>A;
        f.get();
        f>>B;
        memset(a,0,sizeof(a));
        memset(nxt1,-1,sizeof(nxt1));
        memset(nxt2,-1,sizeof(nxt2));
        for(n=0;A[n]>='A'&&A[n]<='Z';++n);
        for(m=0;B[m]>='A'&&B[m]<='Z';++m);
        for(i=n-1;i>=0;--i)
            for(j=m-1;j>=0;--j)
                if(A[i]==B[j])
                    a[i][j]=a[i+1][j+1]+1;
                else
                    a[i][j]=max(a[i+1][j],a[i][j+1]);
        for(i=n-1;i>=0;--i)
            for(j='A';j<='Z';++j)
                if(A[i]==j)
                    nxt1[i][j-'A']=i;
                else
                    nxt1[i][j-'A']=nxt1[i+1][j-'A'];

        for(i=m-1;i>=0;--i)
            for(j='A';j<='Z';++j)
                if(B[i]==j)
                    nxt2[i][j-'A']=i;
                else
                    nxt2[i][j-'A']=nxt2[i+1][j-'A'];

        i=j=0;
        for(;k>=0||(i<n&&j<m);--k)
        {
            for(p=25;p>=0;--p)
                if(nxt1[i][p]>=0&&nxt2[j][p]>=0&&a[nxt1[i][p]][nxt2[j][p]]>=k)
                {
                    g<<(char)(p+'A');
                    i=nxt1[i][p]+1,j=nxt2[j][p]+1;
                    break;
                }
            if(p<0)
                break;
        }
        g<<"\n";
    }
}