#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, x, y, sx, sy;
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;
x = N; y = M;
while(1)
{
caux = '@';
for (i = x; i > 0; i--)
for (j = y; j > 0; j--)
if (S1[i-1]==S2[j-1]&&A[i][j]>=(K-nq))
if (caux<S1[i-1])
caux = S1[i-1], sx = i-1, sy = j-1;
if (caux=='@') break;
Sir[nq++] = caux;
x = sx; y = sy;
}
for (l = nq-1; l >= 0; l--)
{
printf("%c", Sir[l]);
Sir[l] = '\0';
}
printf("\n");
}
return 0;
}