def calc(x,y):

    n = len(x)

    m = len(y)

    dp1 = [0]*(m+1)

    for i in range(n):

        dp2 = dp1[:]

        for j in range(m):

            if x[i] == y[j]:

                dp1[j+1] = dp2[j]+1

            elif dp1[j+1] < dp1[j]:

                dp1[j+1] = dp1[j]

    return dp1[-1]



q = int(eval(input()))

for i in range(q):

    x = eval(input())

    y = eval(input())

    print((calc(x,y)))

def calc(x,y):

    n = len(x)

    m = len(y)

    dp1 = [0]*(m+1)

    for i in range(n):

        s = x[i]

        dp2 = dp1[:]

        for j in range(m):

            if s == y[j]:

                dp1[j+1] = dp2[j]+1

            elif dp1[j+1] < dp1[j]:

                dp1[j+1] = dp1[j]

    return dp1[-1]



q = int(eval(input()))

for i in range(q):

    x = eval(input())

    y = eval(input())

    print((calc(x,y)))

def calc(x, y):
    n = len(x)
    m = len(y)
    dp1 = [0] * (m + 1)
    for i in range(n):
        dp2 = dp1[:]
        for j in range(m):
            if x[i] == y[j]:
                dp1[j + 1] = dp2[j] + 1
            elif dp1[j + 1] < dp1[j]:
                dp1[j + 1] = dp1[j]
    return dp1[-1]


q = int(eval(input()))
for i in range(q):
    x = eval(input())
    y = eval(input())
    print((calc(x, y)))

def calc(x, y):
    n = len(x)
    m = len(y)
    dp1 = [0] * (m + 1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j + 1] = dp2[j] + 1
            elif dp1[j + 1] < dp1[j]:
                dp1[j + 1] = dp1[j]
    return dp1[-1]


q = int(eval(input()))
for i in range(q):
    x = eval(input())
    y = eval(input())
    print((calc(x, y)))

+        s = x[i] -            if x[i] == y[j]: +            if s == y[j]: