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)
ascii_letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'



def llcs(x, y):

    pm = dict((list(zip(ascii_letters, [0] * 52))))

    for c in pm:

        for i, xc in enumerate(x):

            if c == xc:

                pm[c] |= (1 << i)

    

    V = (1 << len(x)) - 1

    

    for yc in y:

        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))

    

    ans = bin(V)[-len(x):].count('0')

    

    return ans



from sys import stdin



def solve():

    file_input = stdin

    q = int(file_input.readline())

    for i in range(q):

        s1 = file_input.readline().rstrip()

        s2 = file_input.readline().rstrip()

        print((llcs(s1, s2)))



solve()

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)

ascii_letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def llcs(x, y):
    pm = dict((list(zip(ascii_letters, [0] * 52))))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= 1 << i
    V = (1 << len(x)) - 1
    for yc in y:
        V = (V + (V & pm[yc])) | (V & ~pm[yc])
    ans = bin(V)[-len(x) :].count("0")
    return ans


from sys import stdin


def solve():
    file_input = stdin
    q = int(file_input.readline())
    for i in range(q):
        s1 = file_input.readline().rstrip()
        s2 = file_input.readline().rstrip()
        print((llcs(s1, s2)))


solve()

-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)) +ascii_letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" -q = int(eval(input())) -for i in range(q): -    ax = eval(input()) -    ay = eval(input()) -    lcs_len(ax, ay) +def llcs(x, y): +    pm = dict((list(zip(ascii_letters, [0] * 52)))) +    for c in pm: +        for i, xc in enumerate(x): +            if c == xc: +                pm[c] |= 1 << i +    V = (1 << len(x)) - 1 +    for yc in y: +        V = (V + (V & pm[yc])) | (V & ~pm[yc]) +    ans = bin(V)[-len(x) :].count("0") +    return ans + + +from sys import stdin + + +def solve(): +    file_input = stdin +    q = int(file_input.readline()) +    for i in range(q): +        s1 = file_input.readline().rstrip() +        s2 = file_input.readline().rstrip() +        print((llcs(s1, s2))) + + +solve()