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

int Case;  
int N, M, K, A[NMAX][NMAX], q[NMAX][2];
char S1[NMAX], S2[NMAX], Sir[NMAX], temp[NMAX];  

int main()  
{  
     int i, j, nq, nt, nsir, l, c, k;  

     freopen("seif.in", "r", stdin);  
     freopen("seif.out", "w", stdout);  
   
     scanf("%d", &Case);  
   
     while (Case--)  
     {  
            scanf("%d", &K);  
            scanf(" %s", S1);  
            scanf(" %s", 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));  
   
            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]>=K)
                         { q[nq][0] = i, q[nq++][1] = j; break; }
   
            for (j = 0; j < nq; j++)  
            {  
                 l = q[j][0]; c = q[j][1];  
                 nt = 0;  
                 k = A[l][c];  
                 while (k>0)  
                 {  
                     if (S1[l-1]==S2[c-1]) {  
                         k--; temp[nt++] = S1[l-1]; l--; c--;  
                        }  
                     else  
                         if ((A[l-1][c]>A[l][c-1])||((A[l-1][c]==A[l][c-1])&&(S1[l-2]>S2[c-2]))) l--;  
                         else c--;  
                 }  
                 for (l = 0; l < nsir; l++)
                      if (Sir[l]!=temp[l]) break;  
                 if (l==nsir||Sir[l]<temp[l])
                 {  
                     for (l = nt-1; l >= 0; l--) Sir[l] = temp[l], temp[l] = '\0';  
                     nsir = nt;  
                 }  
            }  
   
            for (l = 0; l < nsir; l++)  
            {  
                 printf("%c", Sir[l]);  
                 Sir[l] = '\0';  
            }  
            printf("\n");  
     }  
   
     return 0;  
       
}