#include <algorithm>
using namespace std;

#define DIM 1005
#define SIGMA 26

int best[DIM][DIM],poz1[DIM][SIGMA],poz2[DIM][SIGMA];
char s1[DIM],s2[DIM];
int n,m,k,t;

void read ()
{
    scanf ("%d\n",&k);
    fgets (s1+1,DIM,stdin);
    n=strlen (s1+1);
    if (!isalpha (s1[n]))
        --n;
    fgets (s2+1,DIM,stdin);
    m=strlen (s1+1);
    if (!isalpha (s2[m]))
        --m;
}

void solve ()
{
    int i,j;

    memset (best,0,sizeof (best));
    memset (poz1,-1,sizeof (poz1));
	memset (poz2,-1,sizeof (poz2));

    for (i=n; i>=1; --i)
        for (j=m; j>=1; --j)
            if (s1[i]==s2[j])
                best[i][j]=best[i+1][j+1]+1;
            else
                best[i][j]=max (best[i+1][j],best[i][j+1]);
//    for (i=n; i>=1; --i)
//        for (j=0; j<SIGMA; ++j)
//            if (s1[i]==j+'A')
//				poz1[i][j]=i;
//			else
//				poz1[i][j]=poz1[i+1][j];
//    for (i=m; i>=1; --i)
//        for (j=0; j<SIGMA; ++j)
//            if (s2[i]==j+'A')
//				poz2[i][j]=i;
//			else
//				poz2[i][j]=poz2[i+1][j];
    memset(poz1, -1, sizeof poz1);
	for(int i = n; i; --i)
		for(int c = 0; c < SIGMA; ++c)
			if(s1[i] == (c + 'A'))
				poz1[i][c] = i;
			else
				poz1[i][c] = poz1[i+1][c];

	memset(poz2, -1, sizeof poz2);
	for(int i = m; i; --i)
		for(int c = 0; c < SIGMA; ++c)
			if(s2[i] == (c + 'A'))
				poz2[i][c] = i;
			else
				poz2[i][c] = poz2[i+1][c];
}

void print ()
{
    int i,j,l,ok;

    for (ok=i=j=1; ok; )
	{
		ok=0;
		for (l=SIGMA-1; l>=0; --l)
            if (poz1[i][l]!=-1 && poz2[j][l]!=-1 && best[poz1[i][l]][poz2[j][l]]>=k)
			{
                printf ("%c",l+'A');
				i=poz1[i][l]+1;
				j=poz2[j][l]+1;
				ok=1;
				break;
			}
		--k;
	}
	printf ("\n");
}

int main ()
{
    freopen ("seif.in","r",stdin);
    freopen ("seif.out","w",stdout);
    int i;

    scanf ("%d",&t);
    for (i=1; i<=t; ++i)
    {
        read ();
        solve ();
        print ();
    }

    return 0;
}