#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], last[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 <= 26; 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 (S1[i-1]=='K')
S1[i-1] = 'K';
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 = x; l = y;
while ( (y>=0)&&(T[y-1]>(j-1))&&(A[i][j]>=(K-y)) )
l = y, y = last[y];
x = l;
}
else x = y = nq;
while ((Sir[x-1]<S1[i-1])&&(A[i][j]>=(K-x+1))&&(x>0))
x--;
if (x==0) t = 1;
while ((x>0)&&(Sir[x-1]<S1[i-1])&&(T[x-1]<(j-1))&&(A[i][j]>=(K-x+1))&&(x>0))
x--, ok[ T[x] ] = 0, last[x] = -1, F[Sir[x]-'A'] = -1, t = 1;
if (T[x-1]>(j-1)) t = 1;
else
if (x>0) t = 0;
if (t==1)
{
y = nq;
for (l = nq-1; l >= x; l--)
ok[ T[l] ] = 0, last[l] = -1, 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; last[x] = F[ S1[i-1]-'A' ];
F[ S1[i-1]-'A' ] = x;
break;
}
}
for (l = 0; l < nq; l++)
{
printf("%c", Sir[l]);
Sir[l] = '\0';
}
printf("\n");
}
return 0;
}