#include<stdio.h>
#include<string.h>
#define N 1020
int t,n,m,K,v[N][N],T[N],ok[N],i,j,nq,l,x,y,p,q,md;
char s1[N],s2[N],Sir[N],temp[N];
int main(){
	freopen("seif.in","r",stdin);
	freopen("seif.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		memset(s1,'\0',sizeof(s1));
		memset(s2,'\0',sizeof(s2));
		scanf("%d",&K);
		scanf(" ");
		gets(s1);
		scanf(" ");
		gets(s2);
		n=strlen(s1);
		m=strlen(s2);
		for(i=0;i<n;i++)
			temp[i]=s1[n-i-1];
		for(i=0;i<n;i++)
			s1[i]=temp[i];
		for(i=0;i<m;i++)
			temp[i]=s2[m-i-1]; 
		for(i=0;i<m;i++)
			s2[i]=temp[i];
		memset(v,0,sizeof(v));
		memset(T,0,sizeof(T));
		memset(temp,'\0',sizeof(temp));
		memset(Sir,'\0',sizeof(Sir));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				if(s1[i-1]==s2[j-1])
					v[i][j]=v[i-1][j-1]+1;
			else{
				v[i][j]=v[i][j-1];
				if(v[i][j]<v[i-1][j])
					v[i][j]=v[i-1][j];
				}
		nq=x=t=y=0;
		memset(ok,0,sizeof(ok));
		memset(T,0,sizeof(T));
		for(i=n;i>0;i--)   
			for(j=m;j>0;j--)   
				if(!ok[j-1]&&s1[i-1]==s2[j-1]){
					if(nq==0){   
						x=0;   
						if(v[i][j]>=K)
							t=1;   
						else	
							t=0;   
					}
					else{
						x=nq;
						t=0;
						p=0;
						q=nq-1;
						while(p<=q){
							md=(p+q)>>1;
							if((T[md]<j-1)&&(v[i][j]+md>=K))
								q=md-1;
							else
								p=md+1;
					   }
					x=q;
					if(x<0)
						x=0;
					if((T[x]>=j-1)||(v[i][j]+x<K))
						x++;
					if((x>0)&&(T[x-1]<j-1)&&(v[i][j]+x>=K))
						x--;
					//while((x>0)&&(T[x-1]<j-1)&&(v[i][j]+x>=K))
					//	x--;
					if(x>0&&T[x-1]<j-1)
						continue;
					if(x>0&&Sir[x]<s1[i-1])
						t=1;
					//if(x<nq)
					//	x++;
					while((x>0)&&(v[i][j]+x-1>=K)&&(Sir[x-1]<s1[i-1])){
						x--;
						t=1;
					}
					if((x==0&&Sir[0]<s1[i-1])||((x==nq)&&(T[x-1]>j-1)))
						t=1;
					if(v[i][j]+x<K)
						t=0;
					if(t==1)
						for(l=nq-1;l>=x;l--)
							ok[T[l]]=0;
					}
					if(t){
						Sir[x]=s1[i-1];
						T[x++]=j-1;
						nq=x;
						ok[j-1]=1;
						break;
					}
				}
				for(l=0;l<nq;l++){
				printf("%c", Sir[l]);
				Sir[l]='\0';
			}
	printf("\n");
	}
	return 0;
}