#include <bits/stdc++.h>

int A[1001], B[1001];
int N, M;
std::vector <int> GA[256], GB[256];
int d[1001][1001];
int main(){
    FILE*fi,*fo;
    fi = fopen("seif.in","r");
    fo = fopen("seif.out","w");

    int t;
    fscanf(fi,"%d", &t);
    for(int z = 1; z <= t; z++){
        int k;
        fscanf(fi,"%d", &k);

        ///CITIRE
        N = 0;
        M = 0;
        char c = fgetc(fi);
        while(c < 'A' || c > 'Z') c = fgetc(fi);
        while(c >= 'A' && c <= 'Z'){
            A[++N] = c;
            c = fgetc(fi);
        }
        while(c < 'A' || c > 'Z') c = fgetc(fi);
        while(c >= 'A' && c <= 'Z'){
            B[++M] = c;
            c = fgetc(fi);
        }

        ///ROTIRE
        for(int i = 1; i < N - i + 1; i++){
            char aux = A[i];
            A[i] = A[N - i + 1];
            A[N - i + 1] = aux;
        }
        for(int i = 1; i < M - i + 1; i++){
            char aux = B[i];
            B[i] = B[M - i + 1];
            B[M - i + 1] = aux;
        }

        ///INDEXARE
        for(int i = 'A'; i <= 'Z'; i++){
            GA[i].resize(0);
            GB[i].resize(0);
        }
        for(int i = 1; i <= N; i++)
            GA[A[i]].push_back(i);
        for(int i = 1; i <= M; i++)
            GB[B[i]].push_back(i);

        ///CMLSC
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= M; j++)
                if(A[i] == B[j])
                    d[i][j] = 1 + d[i - 1][j - 1];
                else
                    d[i][j] = std::max(d[i - 1][j], d[i][j - 1]);


        while(d[N][M] > 0){
            for(int i = 'A'; i <= 'Z'; i++){
                while(GA[i].size() > 0 && GA[i][GA[i].size() - 1] > N)
                    GA[i].pop_back();
                while(GB[i].size() > 0 && GB[i][GB[i].size() - 1] > M)
                    GB[i].pop_back();
            }
            int i = 'Z';
            while(i >= 'A' && (GA[i].size() == 0 || GB[i].size() == 0 || d[GA[i][GA[i].size() - 1]][GB[i][GB[i].size() - 1]] < k))
                i--;
            fputc(i, fo);
            N = GA[i][GA[i].size() - 1]  - 1;
            M = GB[i][GB[i].size() - 1]  - 1;
            k--;
        }
        fprintf(fo,"\n");
    }

    fclose(fi);
    fclose(fo);
    return 0;
}