#include<stdio.h>   
#include<string.h>   
#define N 1005   
int t,test,n,m,K,v[N][N],T[N],ok[N],i,j,nq,l,x,y,p,q,md;;   
char s1[N],s2[N],Sir[N],temp[N];   
int main(){   
    freopen("seif.in", "r", stdin);   
    freopen("seif.out", "w", stdout);   
    scanf("%d",&test);   
    while(test--){   
        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(v,0,sizeof(v));   
        memset(T,0,sizeof(T));   
        memset(temp,'\0',sizeof(temp));   
        memset(Sir,'\0',sizeof(Sir));   
        for(i=1;i<=n;i++)   
            for(j=1;j<=m;j++)   
                if(s1[i-1]==s2[j-1])   
                    v[i][j]=v[i-1][j-1]+1;   
            else{   
                v[i][j] = v[i][j-1];   
                if(v[i][j]<v[i-1][j])   
                    v[i][j]=v[i-1][j];   
                }   
        nq=x=t=y=0;   
        memset(ok,0,sizeof(ok));   
        memset(T,0,sizeof(T));   
        for(i=n;i>0;i--)      
            for(j=m;j>0;j--)      
                if(!ok[j-1]&&s1[i-1]==s2[j-1]){   
                    if(nq==0){      
                        x=0;      
                        if(v[i][j]>=K)   
                            t=1;      
                        else       
                            t=0;      
                    }   
                    else{   
                        x=nq;   
                        t=0;   
                        p=0;   
                        q=nq-1;   
                        while(p<=q){   
                            md=(p+q)>>1;   
                            if((T[md]<j-1)&&(v[i][j]+md>=K))   
                                q=md-1;   
                            else  
                                p=md+1;   
                       }   
                    x=q;   
                    if(x<0)   
                        x=0;   
                    if((T[x]>=j-1)||(v[i][j]+x<K))   
                        x++;   
                    if((x>0)&&(T[x-1]<j-1)&&(v[i][j]+x>=K))   
                        x--;   
                    if(x>0&&T[x-1]<j-1)   
                        continue;   
                    if(x>0&&Sir[x]<s1[i-1])   
                        t=1;   
                    while((x>0)&&(v[i][j]+x-1>=K)&&(Sir[x-1]<s1[i-1]))
						x--,t=1;
                    if((x==0&&Sir[0]<s1[i-1])||((x==nq)&&(T[x-1]>j-1)))   
                        t=1;   
                    if(v[i][j]+x<K)   
                        t=0;   
                    if(t==1)   
                        for(l=nq-1;l>=x;l--)   
                            ok[T[l]]=0;   
                    }   
                    if(t){   
                        Sir[x]=s1[i-1],T[x++]=j-1;   
                        nq=x;   
                        ok[j-1]=1;   
                        break;   
                    }   
                }   
                for (l=0;l<nq;l++){   
                printf("%c", Sir[l]);   
                Sir[l] = '\0';   
            }   
    printf("\n");   
    }   
    return 0;   
}