from bisect import bisect_left

q = int(eval(input()))

for _ in [0]*q:

    s1, s2 = eval(input()), eval(input())

    l1, l2 = len(s1), len(s2)



    p = []

    for i, c in enumerate(s1):

        s = 0

        while True:

            j = s2[s:].find(c)

            if j == -1:

                break

            p.append((i, s+j))

            s += j+1



    lis = []

    for _, y in sorted(p, key=lambda x: (x[0], -x[1])):

        i = bisect_left(lis, y)

        if len(lis) <= i:

            lis.append(y)

        else:

            lis[i] = y

    print((len(lis)))

def lcs_hs(s1, s2):

    from bisect import bisect_left



    p = []

    append_p = p.append

    for i, c in enumerate(s1):

        j = s2.find(c)+1

        while j:

            append_p((i, -j))

            j = s2.find(c, j)+1



    lis, result = [], 0

    append_lis = lis.append

    for _, y in sorted(p):

        i = bisect_left(lis, -y)

        if i >= result:

            append_lis(-y)

            result += 1

        else:

            lis[i] = -y



    return result





print(*(lcs_hs(input(), input()) for _ in [0]*int(input())), sep="\n")

from bisect import bisect_left

q = int(eval(input()))
for _ in [0] * q:
    s1, s2 = eval(input()), eval(input())
    l1, l2 = len(s1), len(s2)
    p = []
    for i, c in enumerate(s1):
        s = 0
        while True:
            j = s2[s:].find(c)
            if j == -1:
                break
            p.append((i, s + j))
            s += j + 1
    lis = []
    for _, y in sorted(p, key=lambda x: (x[0], -x[1])):
        i = bisect_left(lis, y)
        if len(lis) <= i:
            lis.append(y)
        else:
            lis[i] = y
    print((len(lis)))

def lcs_hs(s1, s2):
    from bisect import bisect_left

    p = []
    append_p = p.append
    for i, c in enumerate(s1):
        j = s2.find(c) + 1
        while j:
            append_p((i, -j))
            j = s2.find(c, j) + 1
    lis, result = [], 0
    append_lis = lis.append
    for _, y in sorted(p):
        i = bisect_left(lis, -y)
        if i >= result:
            append_lis(-y)
            result += 1
        else:
            lis[i] = -y
    return result


print(*(lcs_hs(input(), input()) for _ in [0] * int(input())), sep="\n")

-from bisect import bisect_left +def lcs_hs(s1, s2): +    from bisect import bisect_left -q = int(eval(input())) -for _ in [0] * q: -    s1, s2 = eval(input()), eval(input()) -    l1, l2 = len(s1), len(s2) +    append_p = p.append -        s = 0 -        while True: -            j = s2[s:].find(c) -            if j == -1: -                break -            p.append((i, s + j)) -            s += j + 1 -    lis = [] -    for _, y in sorted(p, key=lambda x: (x[0], -x[1])): -        i = bisect_left(lis, y) -        if len(lis) <= i: -            lis.append(y) +        j = s2.find(c) + 1 +        while j: +            append_p((i, -j)) +            j = s2.find(c, j) + 1 +    lis, result = [], 0 +    append_lis = lis.append +    for _, y in sorted(p): +        i = bisect_left(lis, -y) +        if i >= result: +            append_lis(-y) +            result += 1 -            lis[i] = y -    print((len(lis))) +            lis[i] = -y +    return result + + +print(*(lcs_hs(input(), input()) for _ in [0] * int(input())), sep="\n")