#include <stdio.h>
#include <string.h>
#define NMAX 1005
#define LMAX 27
int t,k,n,m,C[NMAX][NMAX],last[LMAX];
int D[NMAX][LMAX],E[NMAX][LMAX];
char A[NMAX],B[NMAX];
inline int lit(char x)
{
	return x>='A' && x<='Z';
}
void read()
{
	scanf("%d\n",&k);
	n=m=0;
	fgets(A+1,LMAX,stdin);
	fgets(B+1,LMAX,stdin);
	while (lit(A[n+1])) n++;
	while (lit(B[m+1])) m++;
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
void cmlsc()
{
	memset(C,0,sizeof(C));
	memset(D,0,sizeof(D));
	memset(E,0,sizeof(E));
	int i,j;
	for (i=n; i>=1; i--)
		for (j=m; j>=1; j--)
			if (A[i]==B[j])
				C[i][j]=C[i+1][j+1]+1;
			else
				C[i][j]=max(C[i+1][j],C[i][j+1]);
}
void compute_info()
{
	int i,j;
	memset(last,0,sizeof(last));
	for (i=n; i>=0; i--)
	{
		for (j=0; j<=26; j++)
			D[i][j]=last[j];
		last[A[i]-'A']=i;
	}
	memset(last,0,sizeof(last));
	for (i=m; i>=0; i--)
	{
		for (j=0; j<=26; j++)
			E[i][j]=last[j];
		last[B[i]-'A']=i;
	}
}
void solve()
{
	cmlsc();
	compute_info();
	int i,j,ind1=0,ind2=0,poz1,poz2,much=k,ok;
	for (i=1; ; i++)
	{
		ok=0;
		for (j=26; j>=0; j--)
		{
			poz1=D[ind1][j]; poz2=E[ind2][j];
			if (poz1 && poz2 && C[poz1+1][poz2+1]>=much-1)
			{
				ok=1;  much--;
				ind1=poz1; ind2=poz2;
				printf("%c",'A'+j);
				break ;
			}
		}
		if (!ok)
			break ;
	}
	printf("\n");
}
int main()
{
	freopen("seif.in","r",stdin);
	freopen("seif.out","w",stdout);
	scanf("%d",&t);
	while (t--)
	{
		read();
		solve();
	}
	return 0;
}