n = int(eval(input()))

for _ in range(n):

    a, b = eval(input()), eval(input())

    indices = []

    for cb in b:

        bgn_idx = 0

        for i in range(len(indices) + 1):

            chr_idx = a.find(cb, bgn_idx) + 1

            if chr_idx:

                if i < len(indices):

                    bgn_idx = indices[i]

                    if chr_idx < bgn_idx:

                        indices[i] = chr_idx

                else:

                    indices.append(chr_idx)

            else:

                break

    print((len(indices)))
n = int(eval(input()))

for _ in range(n):

    a, b = eval(input()), eval(input())

    indices = []

    for cb in b:

        bgn_idx = 0

        for i, cur_idx in enumerate(indices):

            chr_idx = a.find(cb, bgn_idx) + 1

            if not chr_idx:

                break

            if chr_idx < cur_idx:

                indices[i] = chr_idx

            bgn_idx = cur_idx

        else:

            chr_idx = a.find(cb, bgn_idx) + 1

            if chr_idx:

                indices.append(chr_idx)

    print((len(indices)))
n = int(eval(input()))
for _ in range(n):
    a, b = eval(input()), eval(input())
    indices = []
    for cb in b:
        bgn_idx = 0
        for i in range(len(indices) + 1):
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                if i < len(indices):
                    bgn_idx = indices[i]
                    if chr_idx < bgn_idx:
                        indices[i] = chr_idx
                else:
                    indices.append(chr_idx)
            else:
                break
    print((len(indices)))

n = int(eval(input()))
for _ in range(n):
    a, b = eval(input()), eval(input())
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print((len(indices)))

-        for i in range(len(indices) + 1): +        for i, cur_idx in enumerate(indices): +            chr_idx = a.find(cb, bgn_idx) + 1 +            if not chr_idx: +                break +            if chr_idx < cur_idx: +                indices[i] = chr_idx +            bgn_idx = cur_idx +        else: -                if i < len(indices): -                    bgn_idx = indices[i] -                    if chr_idx < bgn_idx: -                        indices[i] = chr_idx -                else: -                    indices.append(chr_idx) -            else: -                break +                indices.append(chr_idx)