#include <stdio.h>
#include <string.h>

#define fin  "seif.in"
#define fout "seif.out"

const int Nmax  = 1010;
const int sigma = 26;

int T,K,N,M,dp[Nmax][Nmax];
int next1[Nmax][sigma],next2[Nmax][sigma];

char buff1[Nmax],buff2[Nmax];

inline int maxf(int a,int b) { return ( a > b ) ? ( a ) : ( b ); };

void readsolve()
{
	int i,j,k;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	scanf("%i",&T);

	while ( T -- )
	{
		scanf("%i\n",&K);
		fgets(buff1 + 1,Nmax,stdin);
		fgets(buff2 + 1,Nmax,stdin);

		for ( N = 1; 'A' <= buff1[N] && buff1[N] <= 'Z'; ++N);
		--N;
		for ( M = 1; 'A' <= buff2[M] && buff2[M] <= 'Z'; ++M);
		--M;

		memset(next1,0,sizeof(next1));
		memset(next2,0,sizeof(next2));
		memset(dp,0,sizeof(dp));

		for ( i = N; i > 0; --i )
			memcpy(next1[i],next1[i+1],sizeof(next1[i+1])),next1[i][buff1[i]-'A']=i;
		for ( i = M; i > 0; --i )
			memcpy(next2[i],next2[i+1],sizeof(next2[i+1])),next2[i][buff2[i]-'A']=i;

		for ( i = N; i > 0; --i )
		for ( j = M; j > 0; --j )
			if ( buff1[i] == buff2[j] )
				dp[i][j] = dp[i+1][j+1] + 1;
			else
				dp[i][j] = maxf(dp[i+1][j],dp[i][j+1]);

		i = j = 1;

        int flag;
        
		for ( ; ; )
		{
            flag = 0;
            
			for ( k = sigma - 1; k >= 0; --k )
				if ( next1[i][k] && next2[j][k] && dp[ next1[i][k] ][ next2[j][k] ] >= K )
				{
					i = next1[i][k] + 1;
					j = next2[j][k] + 1;
					printf("%c",k+'A');
					flag = 1;
					break;
				}
			if ( !flag ) break;
			--K;
		}
		
        printf("\n");
	}
}

int main()
{
	readsolve();
	return 0;
}