#include <fstream>
using namespace std;
ifstream cin("seif.in");
ofstream cout("seif.out");
int dp[1005][1005];
string bst[1005];
string a,b;
int main()
{
    int tst,k,n,m;
    cin>>tst;
    while(tst--)
    {
        cin>>k;
        cin>>a>>b;
        n=a.size();
        m=b.size();
        for(int i=1;i<=n;++i)
            dp[i][0]=0;
        for(int j=1;j<=m;++j)
            dp[0][j]=0;
        for(int i=0;i<=min(n,m);++i)
            bst[i]="";
        int maxim=0;
        for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                if(dp[i][j]>maxim)
                    maxim=dp[i][j];
                for(int r=maxim;r>=1;--r)
                    bst[r]=max(bst[r],bst[r-1]+a[i-1]);
            }
            else if(dp[i][j-1]<dp[i-1][j])
                dp[i][j]=dp[i-1][j];
            else dp[i][j]=dp[i][j-1];
        }
        string ans=bst[k];
        for(int i=k+1;i<=min(n,m);++i)
            ans=max(ans,bst[i]);
        cout<<ans<<'\n';
    }
    return 0;
}