def lcs(string1, string2):
    len1 = len(string1)
    len2 = len(string2)
    max_index = []
    max_length = 0
    current_length = 0
    start_index = 0
    final = []
    for i in range(len1):
        for j in range(len2):
            if (string1[i + current_length: i + 1 + current_length] == string2[j: j + 1]):
                if (current_length > 0):
                    current_length += 1
                else:
                    current_length = 1
                    start_index = i
            else:
                if (current_length >= max_length):
                    if (current_length == max_length):
                        max_index.append(start_index)
                    elif (current_length > max_length):
                        max_length = current_length
                        max_index = [start_index]
                    current_length = 0
                    start_index = 0
                else:
                    current_length = 0
                    start_index = 0
        if (current_length >= max_length):
            if (current_length == max_length):
                max_index.append(start_index)
            elif (current_length > max_length):
                max_length = current_length
                max_index = [start_index]
            current_length = 0
            start_index = 0
        else:
            current_length = 0
            start_index = 0
    for i in (max_index):
        final.append(string1[i: i + max_length])
    final = sorted(final)
    return final[0]

def commonstring(initial_list):
    phrase1 = initial_list[0]
    phrase2 = initial_list[1]
    ADP = 0
    if phrase1 == "" or phrase2 == "":
        return 0

    common_string = lcs(initial_list[0], initial_list[1])
    if common_string == "":
        return 0
    ADP += len(common_string)

    p1_index = phrase1.index(common_string)
    p2_index = phrase2.index(common_string)
    left_list = [phrase1[0: p1_index], phrase2[0: p2_index]]
    right_list = [phrase1[p1_index + len(common_string):], phrase2[p2_index + len(common_string):]]

    ADP += commonstring(left_list)
    ADP += commonstring(right_list)
    return ADP

for cases in range (0,5):
    inputs = [''.join([i for i in input("String 1: ") if i.isalpha()]).upper(), ''.join([i for i in input("String 2: ") if i.isalpha()]).upper()]
    print(commonstring(inputs))

#I am going home now
#I will go home now
#The big black bear bit a big black bug
#The big black bug bled black blood
#Complementary angle measures sum to 90 degrees.
#The measures of supplementary angles add to 180 degrees.
#A Tale of Two Cities was published by Dickens in 1859.
#In 1839, Charles Dickens published Nicholas Nickleby.
#Connecticut is The Constitution State.
#Hartford is the capital of Connecticut.