#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];
}

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 i(1), j(1), ok(1);

	while(ok)
	{
		ok = 0;
		for(int c = 25; c >= 0; --c)
			if((poz1[i][c] != -1) && (poz2[j][c] != -1) && (best[poz1[i][c]][poz2[j][c]] >= k))
			{
				printf("%c",c + 'A');
				ok = 1;
				i = poz1[i][c] + 1;
				j = poz2[j][c] + 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;
}