# Arup Guha
# 7/24/2014
# Solution to 2014 SI@UCF Final Contest Problem: Baby Names

# Note: This is very slow since I store each LCS, but easier to implement.

def main():

    myFile = open("names.in")
    numCases = int(myFile.readline().strip())

    # Go through each case.
    for loop in range(numCases):

        # Get input.
        line = myFile.readline().split()
        mom = line[0]
        dad = line[1]

        # Store all best strings here, set up each row of dp array.
        dp = []
        for i in range(len(mom)+1):
            dp.append([])

        # All LCS's with empty strings are empty.
        for i in range(len(dad)+1):
            dp[0].append("")

        # Go through each row of the DP array.
        for i in range(1, len(mom)+1):
            dp[i].append("")

            # Go through each column.
            for j in range(1, len(dad)+1):

                # Characters match, take it!
                if mom[i-1] == dad[j-1]:
                    dp[i].append(dp[i-1][j-1]+str(mom[i-1]))

                # Take the better or our two options.
                else:
                    if len(dp[i-1][j]) > len(dp[i][j-1]):
                        dp[i].append(dp[i-1][j])
                    else:
                        dp[i].append(dp[i][j-1])

        # Here is our result.
        print(dp[len(mom)][len(dad)])

    myFile.close()
                                      
main()