/* Dynamic Programming C/C++ implementation of LCS problem */
//#include<bits/stdc++.h>

//int max(int a, int b);

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
//int lcs( char *X, char *Y, int m, int n )
//{
//    int L[m+1][n+1];
//    int i, j;

    /* Following steps build L[m+1][n+1] in bottom up fashion. Note
     that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
/*    for (i=0; i<=m; i++)
    {
        for (j=0; j<=n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;

            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;

            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
    */
    /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
//    return L[m][n];
//}

/* Utility function to get max of 2 integers */
//int max(int a, int b)
//{
//    return (a > b)? a : b;
//}
//
// Driver program to test above function
//int main()
/*{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";

    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS is %d", lcs( X, Y, m, n ) );

    return 0;
} */



//lcs(string a, string b, int n, int m)

/*function LCSLength(X[1..m], Y[1..n])
 C = array(0..m, 0..n)
 for i := 0..m
 C[i,0] = 0
 for j := 0..n
 C[0,j] = 0
 for i := 1..m
 for j := 1..n
 if X[i] = Y[j]
 C[i,j] := C[i-1,j-1] + 1
 else
 C[i,j] := max(C[i,j-1], C[i-1,j])
 return C[m,n]*/

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
string a, b, s;
int c[2002][2002];

//https://pastebin.com/ssKN9aKj

int main (){

    int t, n, m;
    cin>> t;

    for(int k=0; k<t; k++){

        cin >> n>> m;
        cin >> a;
        cin >> b;   // Y: b   N: b[i]

        s = "";  // 清空s
//        for(int i=0; i<n; i++)
//        for(int i=0; i<m; i++)

        //    char ans[200];

//        cout << a <<b;

//        int cnt=0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m;j++){

                 if(a[i-1]==b[j-1]){
                    c[i][j]=c[i-1][j-1]+1;
                    }
                else c[i][j]=max(c[i][j-1], c[i-1][j]); //DEBUGGGED  c[i-1][j-1]
                }
        }
        int nowi=n, nowj=m;

        while(nowi!=0&&nowj!=0){
            if(a[nowi-1]==b[nowj-1]){  //DEBUGGED  b[nowj-1]
                s+=a[nowi-1];
                nowi--;
                nowj--;
            }
            else if(c[nowi-1]==0) nowj--;
            else if(c[nowj-1]==0) nowi--;
            else if(c[nowi-1][nowj]>c[nowi][nowj-1]) nowi--;
            else nowj--;
        }
        reverse(s.begin(), s.end());
        cout << s;

        if(c[n][m]==0) cout << "*";
    //    else for(int i=0; i<cnt; i++)  cout << ans << endl;
        cout << endl;

    }
}

//char a = '4';
//s[0]+=a;
//reverse(a.begin(), a.end());