import sys

readline = sys.stdin.readline

from collections import defaultdict

from bisect import bisect_left, bisect, insort_left, insort

INF = 10000

def lcs(s1, s2):

    c = defaultdict(list)

    for i, s in enumerate(s1):

        c[s].append(i)

    for s in set(s2):

        c[s].append(INF)

    dp = []

    for s2_k in s2:

        bgn_idx = 0

        for i, cur_idx in enumerate(dp):

            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)]

            if chr_idx == INF:

                break

            dp[i] = min(cur_idx, chr_idx + 1)

            bgn_idx = cur_idx

        else:

            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)]

            if chr_idx != INF:

                dp.append(chr_idx + 1)

    return len(dp)

def solve():

    N = int(eval(input()))

    for _ in range(N):

        x = readline().strip()

        y = readline().strip()

        print((lcs(x, y) if len(x) < len(y) else lcs(y, x)))

solve()



for _ in range(int(eval(input()))):

    a = eval(input())

    b = eval(input())

    if len(a) < len(b):

        a, b = b, a

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

import sys

readline = sys.stdin.readline
from collections import defaultdict
from bisect import bisect_left, bisect, insort_left, insort

INF = 10000


def lcs(s1, s2):
    c = defaultdict(list)
    for i, s in enumerate(s1):
        c[s].append(i)
    for s in set(s2):
        c[s].append(INF)
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)]
            if chr_idx == INF:
                break
            dp[i] = min(cur_idx, chr_idx + 1)
            bgn_idx = cur_idx
        else:
            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)]
            if chr_idx != INF:
                dp.append(chr_idx + 1)
    return len(dp)


def solve():
    N = int(eval(input()))
    for _ in range(N):
        x = readline().strip()
        y = readline().strip()
        print((lcs(x, y) if len(x) < len(y) else lcs(y, x)))


solve()

for _ in range(int(eval(input()))):
    a = eval(input())
    b = eval(input())
    if len(a) < len(b):
        a, b = b, a
    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)))

-import sys - -readline = sys.stdin.readline -from collections import defaultdict -from bisect import bisect_left, bisect, insort_left, insort - -INF = 10000 - - -def lcs(s1, s2): -    c = defaultdict(list) -    for i, s in enumerate(s1): -        c[s].append(i) -    for s in set(s2): -        c[s].append(INF) -    dp = [] -    for s2_k in s2: +for _ in range(int(eval(input()))): +    a = eval(input()) +    b = eval(input()) +    if len(a) < len(b): +        a, b = b, a +    indices = [] +    for cb in b: -        for i, cur_idx in enumerate(dp): -            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)] -            if chr_idx == INF: +        for i, cur_idx in enumerate(indices): +            chr_idx = a.find(cb, bgn_idx) + 1 +            if not chr_idx: -            dp[i] = min(cur_idx, chr_idx + 1) +            if chr_idx < cur_idx: +                indices[i] = chr_idx -            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)] -            if chr_idx != INF: -                dp.append(chr_idx + 1) -    return len(dp) - - -def solve(): -    N = int(eval(input())) -    for _ in range(N): -        x = readline().strip() -        y = readline().strip() -        print((lcs(x, y) if len(x) < len(y) else lcs(y, x))) - - -solve() +            chr_idx = a.find(cb, bgn_idx) + 1 +            if chr_idx: +                indices.append(chr_idx) +    print((len(indices)))