#include <stdio.h>  
#include <string.h>  
#define MAX 1011
int Case,N, M, K, A[MAX][MAX], T[MAX], ok[MAX];
char S1[MAX], S2[MAX], Sir[MAX], temp[MAX];
int main(){  
     int i, j, nq, l, t, x, y, p, q, md;
     freopen("seif.in", "r", stdin);  
     freopen("seif.out", "w", stdout);
     scanf("%d", &Case);
     while (Case--){
            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(A,0,sizeof(A));
            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])
					 A[i][j] = A[i-1][j-1]+1;
                 else{  
                     A[i][j] = A[i][j-1];  
                     if (A[i][j]<A[i-1][j]) A[i][j] = A[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 (A[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)&&(A[i][j]+md >= K)) q = md-1;
                                else p = md+1;
                       }
					   x = q;
                       if (x<0) 
						   x = 0;
					   if ( (T[x] >= j-1)||(A[i][j]+x < K) )
						   x++;
                       if ( (x>0)&&(T[x-1] < j-1)&&(A[i][j]+x >= K) ) 
						   x--;
					   if (x>0&&T[x-1] < j-1)
						   continue;
					   if (x>0&&Sir[x]<S1[i-1])
						   t = 1;
					   while ( (x>0) && (A[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 (A[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;
}