def lcs_len(x, y):

    ly = len(y)

    tcsl = [0] * (ly + 1)

    for x_i in x:

        pre_tcsl = list(tcsl)

        for j in range(ly):

            if x_i == y[j]:

                tcsl[j] = pre_tcsl[j - 1] + 1

            elif tcsl[j] < tcsl[j - 1]:

                tcsl[j] = tcsl[j - 1]

    print((tcsl[j]))





q = int(eval(input()))



for i in range(q):

    ax = eval(input())

    ay = eval(input())

    lcs_len(ax, ay)
def lcs_len(x, y):

    indices = [0]

    for y_i in y:

        t_index = 0

        for i, index in enumerate(indices, 1):

            c_index = x.find(y_i, t_index) + 1

            if c_index:

                if i < len(indices):

                    t_index = indices[i]

                    indices[i] = min(c_index, t_index)

                else:

                    indices.append(c_index)

                    break

    print((len(indices) - 1))





q = int(eval(input()))



for i in range(q):

    ax = eval(input())

    ay = eval(input())

    lcs_len(ax, ay)
def lcs_len(x, y):
    ly = len(y)
    tcsl = [0] * (ly + 1)
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            elif tcsl[j] < tcsl[j - 1]:
                tcsl[j] = tcsl[j - 1]
    print((tcsl[j]))


q = int(eval(input()))
for i in range(q):
    ax = eval(input())
    ay = eval(input())
    lcs_len(ax, ay)

def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print((len(indices) - 1))


q = int(eval(input()))
for i in range(q):
    ax = eval(input())
    ay = eval(input())
    lcs_len(ax, ay)

-    ly = len(y) -    tcsl = [0] * (ly + 1) -    for x_i in x: -        pre_tcsl = list(tcsl) -        for j in range(ly): -            if x_i == y[j]: -                tcsl[j] = pre_tcsl[j - 1] + 1 -            elif tcsl[j] < tcsl[j - 1]: -                tcsl[j] = tcsl[j - 1] -    print((tcsl[j])) +    indices = [0] +    for y_i in y: +        t_index = 0 +        for i, index in enumerate(indices, 1): +            c_index = x.find(y_i, t_index) + 1 +            if c_index: +                if i < len(indices): +                    t_index = indices[i] +                    indices[i] = min(c_index, t_index) +                else: +                    indices.append(c_index) +                    break +    print((len(indices) - 1))