#include<fstream>
#include<cstring>
#define DIM 1003
using namespace std;
char s1[DIM],s2[DIM];
int poz1[DIM][DIM],poz2[DIM][DIM],best[DIM][DIM],t,n,m,k;
int main()
{
	ifstream fin("seif.in");
	freopen("seif.out","wt",stdout);
	fin>>t;
	while(t)
	{
		--t;
		fin>>k;
		fin.get();
		fin.getline(s1,DIM);
		fin.getline(s2,DIM);
		n=strlen(s1)-1;
		m=strlen(s2)-1;
		int i,j;
		for(i=n;i>=0;i--)
		   for(j=m;j>=0;j--)
		      if(s1[i]==s2[j])
		        best[i][j]=best[i+1][j+1]+1;
		      else
		        best[i][j]=max(best[i+1][j],best[i][j+1]);
		 for(i=n+1;i>=0;i--)
		    for(j=0;j<26;j++)
		       poz1[i][j]=-1;
		 for(i=m+1;i>=0;i--)
		    for(j=0;j<26;j++)
		       poz2[i][j]=-1;
		 for(i=n;i>=0;i--)
		    for(j=0;j<26;j++)
		       if(j+'A'==s1[i])
		         poz1[i][j]=i;
		       else
		         poz1[i][j]=poz1[i+1][j];
		 for(i=m;i>=0;i--)
		    for(j=0;j<26;j++)
		       if(j+'A'==s2[i])
		         poz2[i][j]=i;
		       else
		         poz2[i][j]=poz2[i+1][j];   
		 i=j=0;
		 for(;k>=0 || (i!=-1 && j!=-1);k--)
		 {
			 int kk;
			 for(kk=25;kk>=0;kk--)
			    if(poz1[i][kk]!=-1 && poz2[j][kk]!=-1 && best[poz1[i][kk]][poz2[j][kk]]>=k)
			      { 
			         printf("%c",kk+'A');
			         i=poz1[i][kk]+1;
			         j=poz2[j][kk]+1;
			         break;
				   }
			  if(kk==-1)
			     break;
			 } 
			printf("\n");   
		 }
}