#include <stdio.h>
#include <string.h>
int n, m, t, k;
int d[1005][1005];
int pred1[1005][28], pred2[1005][28];
char s1[1005], s2[1005];
inline int max (int a, int b) {return a > b ? a : b;}
int main ()
{
freopen ("seif.in", "r", stdin);
freopen ("seif.out", "w", stdout);
scanf ("%d", &t);
int i, j, l;
while (t --)
{
memset (d, 0, sizeof (d));
memset (pred1, 0, sizeof (pred1));
memset (pred2, 0, sizeof (pred2));
scanf ("%d\n", &k);
gets (s1 + 1);
gets (s2 + 1);
n = strlen (s1 + 1);
m = strlen (s2 + 1);
for (i = n; i >= 1; i --)
for (j = m; j >= 1; j --)
if (s1[i] == s2[j])
d[i][j] = d[i + 1][j + 1] + 1;
else
d[i][j] = max (d[i + 1][j], d[i][j + 1]);
for (i = n; i >= 1; i --)
for (j = 0; j < 26; j ++)
if (s1[i] - 'A' == j)
pred1[i][j] = i;
else
pred1[i][j] = pred1[i + 1][j];
for (i = m; i >= 1; i --)
for (j = 0; j < 26; j ++)
if (s2[i] - 'A' == j)
pred2[i][j] = i;
else
pred2[i][j] = pred2[i + 1][j];
i = j = 1;
for (; k >= 0 || (i <= n && j <= m); k --)
{
for (l = 25; l >= 0; l --)
if (pred1[i][l] && pred2[j][l] && d[pred1[i][l]][pred2[j][l]] >= k)
{
printf ("%c", l + 'A');
i = pred1[i][l] + 1;
j = pred2[j][l] + 1;
break;
}
if (l < 0)
break;
}
printf ("\n");
}
return 0;
}