///started at 12:30
///finished at 12:50
///final check at 12:51
///submited
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

FILE *f = fopen("seif.in","r");
FILE *g = fopen("seif.out","w");

const int TMAX = 10;
const int NMAX = 1000;
const int SIGMA = 'z' - 'a' + 1;


int t;
char a[NMAX + 5];
char b[NMAX + 5];
int len_a,len_b;
int nxt_a[NMAX + 5][SIGMA + 5];
int nxt_b[NMAX + 5][SIGMA + 5];


short dp[NMAX + 5][NMAX + 5];

int main(){

    fscanf(f,"%d\n",&t);

    while(t--){
        int k;
        fscanf(f,"%d\n",&k);
        fgets(a + 1,NMAX + 5,f);len_a = strlen(a + 1);len_a -= (a[len_a] == '\n');
        fgets(b + 1,NMAX + 5,f);len_b = strlen(b + 1);len_b -= (b[len_b] == '\n');

        for(int i = 1;i <= len_a;i++){
            a[i] += 'a' - 'A';
        }

        for(int i = 1;i <= len_b;i++){
            b[i] += 'a' - 'A';
        }

        for(int i = len_a;i;i--){
            for(int j = 0;j < SIGMA;j++){
                nxt_a[i][j] = (i < len_a ? nxt_a[i + 1][j]:-1);
            }
            if(i < len_a){
                nxt_a[i][a[i + 1] - 'a'] = i + 1;
            }
        }

        for(int i = len_b;i;i--){
            for(int j = 0;j < SIGMA;j++){
                nxt_b[i][j] = (i < len_b ? nxt_b[i + 1][j]:-1);
            }
            if(i < len_b){
                nxt_b[i][b[i + 1] - 'a'] = i + 1;
            }
        }

        for(int i = len_a;i;i--){
            for(int j = len_b;j;j--){
                dp[i][j] = 0;
                dp[i][j] = max(dp[i][j],short(i < len_a ? dp[i + 1][j]:0));
                dp[i][j] = max(dp[i][j],short(j < len_b ? dp[i][j + 1]:0));
                dp[i][j] = max(dp[i][j],short((i < len_a && j < len_b ? dp[i + 1][j + 1]:0) + (a[i] == b[j])));
            }
        }

        int x = 1;
        int y = 1;
        bool ok = true;

        while(ok){
            if(a[x] == b[y]){
                fputc(a[x] + 'A' - 'a',g);
                k--;
            }
            ok = false;
            for(int c = 'z' - 'a';c >= 0;c--){
                if(nxt_a[x][c] != -1 && nxt_b[y][c] != -1 && dp[nxt_a[x][c]][nxt_b[y][c]] >= k){
                    x = nxt_a[x][c];
                    y = nxt_b[y][c];
                    ok = true;
                    break;
                }
            }
        }
        fputc('\n',g);
    }

    fclose(f);
    fclose(g);

    return 0;
}