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

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

int main()  
{  
     int i, j, nq, nt, l, c, k , ns, poz, start;

     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(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 = 0;  

            for (i = 1; i <= N; i++)  
                 for (j = M; j > 0; j--)  
                     if (S1[i-1]==S2[j-1]&&A[i][j])
                     {
                         temp[nq++] = S1[i-1];
                         break;
                     }
   

            memset(L,0,sizeof(L));
            saux = '@';
            for (j = 0; j < nq; j++)
            {
                caux = '@'; poz = -1;
                for (l = j-1; l >= 0; l--)
                    if ((temp[l]>caux)&&((L[l]+nq-j)>=K))
                       caux = temp[l], poz = l;
                if (poz>=0) L[j] = L[poz]+1, cL[j] = poz;
                else L[j] = 1;
                if (L[j]>=K)
                   if ( (temp[j]>saux)||(temp[j]==saux&&L[j]>L[start]) )
                      saux = temp[j], start = j;
            }

            ns = 0;
            while (start)
                  Sir[ns++] = temp[start], start = cL[start];
            Sir[ns++] = temp[start];
   
            for (l = ns-1; l >= 0; l--)
            {  
                 printf("%c", Sir[l]);
                 Sir[l] = '\0';  
            }  
            printf("\n");  
     }  
   
     return 0;  
       
}