#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;
}