#include <stdio.h>
#include <algorithm>

using namespace std;

#define NMAX 1024
#define SIGMA 255

int din[NMAX][NMAX];
int lstA[NMAX][SIGMA],lstB[NMAX][SIGMA];
char A[NMAX],B[NMAX];

void compute()
{
	int n,m,k;
	int c,i,j,x,y;

	scanf("%d\n",&k);

	fgets(A,NMAX,stdin);
	fgets(B,NMAX,stdin);

	for (n=0;A[n]>='A'&&A[n]<='Z';n++);
	for (m=0;B[m]>='A'&&B[m]<='Z';m++);

	reverse(A,A+n);
	reverse(B,B+m);

	memset(din,0,sizeof(din));

	for (i=1;i<=n;i++)
		for (j='A';j<='Z';j++)
			if (A[i-1]==j) lstA[i][j]=i;
				else lstA[i][j]=lstA[i-1][j];

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

	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (A[i-1]==B[j-1]) din[i][j]=din[i-1][j-1]+1;
				else din[i][j]=max(din[i-1][j],din[i][j-1]);
	
	char sol[NMAX],L;
	L=-1;
	i=n;j=m;

	while (i&&j)
	    	for (c='Z';c>='A';c--)
		{
			x=lstA[i][c];
			y=lstB[j][c];
			
			if (x&&y&&din[x][y]>=k) {sol[++L]=c;
						    i=x-1;j=y-1;
	                                            k--;
						    break;} 
		}
	for (i=0;i<=L;i++) printf("%c",sol[i]);
	printf("\n");
}

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

	int T;
	scanf("%d",&T);

	for (;T;T--)
		compute();
	return 0;
}