#include <stdio.h>  
#include <string.h>  
#define NMAX 1011  

int Case;  
int N, M, K, A[NMAX][NMAX], q[NMAX*NMAX][2], T[NMAX], ok[NMAX], F[NMAX];
char S1[NMAX], S2[NMAX], Sir[NMAX], temp[NMAX], caux, saux;

int main()  
{  
     int i, j, nq, nt, l, c, t, x, y, sx, sy, min;
     
     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));
   
            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 = 0;

            memset(ok,0,sizeof(ok));
            for (i = 0; i < N; i++) F[i] = -1;
            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, t = 1;
                   else
                   {
                       t = S1[i-1]-'A';

                       for (l = 0, min = 666000666; l < t; l++)
                           if ((F[l]>=0)&&(min>F[l]&&(A[i][j]>=(K-F[l]))&&(T[ F[l]-1 ]>(j-1)))) min = F[l];

                       t = 0;
                       if (min<666000666) x = min+1, y = min+1;
                       else x = y = nq;

                       while ((Sir[x-1]<S1[i-1])&&(A[i][j]>=(K-x+1))&&(x>0))
                             x--, ok[ T[x] ] = 0, F[Sir[x]-'A'] = -1, t = 1;
                       while ((Sir[x-1]<S1[i-1])&&(T[x-1]<(j-1))&&(A[i][j]>=(K-x+1))&&(x>0))
                             x--, ok[ T[x] ] = 0, F[Sir[x]-'A'] = -1, t = 1;
                       if (T[x-1]>(j-1)) t = 1;
                       else
                           if (x>0) t = 0;
                       if (t==1)
                       {
                          for (l = y; l < nq; l++)
                              ok[ T[l] ] = 0, F[ Sir[l]-'A' ] = -1;
                       }
                   }
                   if (t&&A[i][j]>=(K-x))
                   {
                      Sir[x] = S1[i-1], nq = x+1, T[x] = j-1;
                      ok[j-1] = 1; F[ S1[i-1]-'A' ] = x;
                      break;
                   }
               }

            for (l = 0; l < nq; l++)
            {  
                 printf("%c", Sir[l]);
                 Sir[l] = '\0';  
            }  
            printf("\n");  
     }  
   
     return 0;  
       
}