#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 1010

int n,m,k;
char s1[N],s2[N];
int a[N][N];
int poz1[30][N],poz2[30][N];

inline void refresh() {
	for(int i=0; i<26; ++i)
		poz1[i][0] = poz2[i][0] = 0;
}

inline int get(char x) {
	return ((int)(x-'A'));
}

inline int maxim(int &x,int &y) {
	return ((x>y) ? x : y);
}

inline void citire() {
	scanf("%d\n",&k);
	fgets(s1+1,N-1,stdin);
	fgets(s2+1,N-1,stdin);

	for(n=1; 'A'<=s1[n] && s1[n]<='Z'; ++n)
		;
	--n;
	for(m=1; 'A'<=s2[m] && s2[m]<='Z'; ++m)
		;
	--m; 

	for(int i=1,j=n; i<j; ++i,--j)
		swap(s1[i],s1[j]);
	for(int i=1,j=m; i<j; ++i,--j)
		swap(s2[i],s2[j]);

	for(int i=1; i<=n; ++i)
		poz1[get(s1[i])][++poz1[get(s1[i])][0]] = i;
	for(int i=1; i<=m; ++i)
		poz2[get(s2[i])][++poz2[get(s2[i])][0]] = i;
}

inline void precalc() {
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			if(s1[i]==s2[j])
				a[i][j] = a[i-1][j-1]+1;
			else
				a[i][j] = maxim(a[i][j-1],a[i-1][j]);
		}
	}
}

inline void scrie() {
	int p1=n,p2=m;
	bool found;

	while(p1>0 && p2>0) {
		found = false;
		for(int i=25; i>=0; --i) {
			while(poz1[i][0]>0 && poz1[i][poz1[i][0]]>p1)
				--poz1[i][0];
			if(poz1[i][0]==0)
				continue;
			while(poz2[i][0]>0 && poz2[i][poz2[i][0]]>p2)
				--poz2[i][0];
			if(poz2[i][0]==0)
				continue;

			if(a[poz1[i][poz1[i][0]]][poz2[i][poz2[i][0]]]>=k) {
				p1 = poz1[i][poz1[i][0]]-1;
				p2 = poz2[i][poz2[i][0]]-1;
				fputc((int)'A'+i,stdout);
				--k;
				found = true;
				break;
			}
		}
		if(!found)
			exit(4);
	}
	fputc('\n',stdout);
}

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

	int T;
	scanf("%d",&T);
	for(; T>0; --T) {
		refresh();
		citire();
		precalc();
		scrie();
	}

	return 0;
}