#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][200],nxt2[maxn][200],p;
string A,B;

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));
        n=A.size();
        m=B.size();
        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]=i;
                else
                    nxt1[i][j]=nxt1[i+1][j];

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

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