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")

def lcs_hs(s1, s2):

    from bisect import bisect_left



    s2 = s2[::-1]

    lis, result = [], 0

    append = lis.append



    for c in s1:

        i = s2.find(c)+1

        while i:

            j = bisect_left(lis, -i)

            if j >= result:

                append(-i)

                result += 1

            else:

                lis[j] = -i

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



    return result





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



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")

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

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


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

-    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 +    s2 = s2[::-1] -    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 +    append = lis.append +    for c in s1: +        i = s2.find(c) + 1 +        while i: +            j = bisect_left(lis, -i) +            if j >= result: +                append(-i) +                result += 1 +            else: +                lis[j] = -i +            i = s2.find(c, i) + 1