#include <stdio.h>
#include <string.h>
#define NMAX 1005
#define LMAX 27
int t,k,n,m,C[NMAX][NMAX];
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;
	for (i=n; i>=0; i--)
		for (j=0; j<=26; j++)
		{
			if (A[i]=='A'+j)
				D[i][j]=i;
			else
				D[i][j]=D[i+1][j];
		}
	for (i=m; i>=0; i--)
		for (j=0; j<=26; j++)
		{
			if (B[i]=='A'+j)
				E[i][j]=i;
			else
				E[i][j]=E[i+1][j];
		}
}
void solve()
{
	cmlsc();
	compute_info();
	int i,j,ind1=1,ind2=1,poz1,poz2,ok=1;
	for (i=1; ok ; i++)
	{
		ok=0;
		for (j=26; j>=0; j--)
		{
			poz1=D[ind1][j]; poz2=E[ind2][j];
			if (poz1 && poz2 && C[poz1][poz2]>=k)
			{
				ok=1;  k--;
				ind1=poz1+1; ind2=poz2+1;
				printf("%c",'A'+j);
				break ;
			}
		}
	}
	printf("\n");
}
int main()
{
	freopen("seif.in","r",stdin);
	freopen("seif.out","w",stdout);
	scanf("%d\n",&t);
	while (t--)
	{
		read();
		solve();
	}
	return 0;
}