CodeEff/ECCO huggingface dataset:
# Original solution
#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")



# Optimized solution
#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
# Original solution
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")


# Optimized solution
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")
# Original solution
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")



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

    s2, lis, result = s2[::-1], [], 0
    find, append = s2.find, lis.append

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

    return result


print(*(lcs_hs(input(), input()) for _ in [0]*int(input())), sep="\n")
# Original solution
from itertools import chain
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    # x = " " + x
    # y = " " + y
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(chain.from_iterable(c))


n = int(input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")


# Optimized solution

from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(n + 1) for a in range(m + 2)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(max(c))

n = int(input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")
# Original solution
def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        c2 = c1[:]
        for j in range(b):
            if x[i] == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")


# Optimized solution
def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")
# Original solution
q = int(input().rstrip())
ans = []
for i in range(q):
    x = input().rstrip()
    y = input().rstrip()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    ans.append(dp1[-1])
print(*ans, sep="\n")


# Optimized solution
def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input().rstrip())
ans = []
for i in range(q):
    x = input()
    y = input()
    ans.append(calc(x,y))
print(*ans, sep="\n")
# Original solution
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = input()
	s2 = input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			else:
				dp1[j + 1] = dp1[j] if dp1[j] > dp2[j + 1] else dp2[j + 1]

	return dp1[-1]

tc = int(input())
for _ in range(tc):
	print((lcs()))

# Optimized solution
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = input()
	s2 = input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			elif dp1[j + 1] < dp1[j]:
				dp1[j + 1] = dp1[j]

	return dp1[-1]

if __name__ == '__main__':
	tc = int(input())
	for _ in range(tc):
		print((lcs()))
# Original solution
def lcs(X, Y):
    m = len(X) + 1
    n = len(Y) + 1
    c = [[0] * n for _ in range(m)]
    X = ' ' + X
    Y = ' ' + Y
    maxl = 0
    for i in range(1,m):
        for j in range(1,n):
            if X[i] == Y[j]:
                c[i][j] = c[i-1][j-1] + 1
            #elif c[i-1][j] >= c[i][j-1]:
            #    c[i][j] = c[i-1][j]
            else:
                c[i][j] = max(c[i][j-1],c[i-1][j])
        maxl = max(maxl, c[i][j])
    print(maxl)
    return 0

def main():
    q = int(input())
    for i in range(q):
        X = input()
        Y = input()
        lcs(X,Y)
    return 0

main()

# Optimized solution
def lcs(x,y):
    a, b = len(x), len(y)
    x1 = [0 for k in range(b+1)]
    for i in range(a):
        e = x[i]
        x2 = x1+[]
        for j in range(b):
            if e == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    print(max(x1))
    return 0

def main():
    q = int(input())
    for i in range(q):
        X = input()
        Y = input()
        lcs(X,Y)
    return 0

main()
# Original solution
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()



# Optimized solution
import sys
readline = sys.stdin.readline
for _ in range(int(eval(input()))):
    a = readline().strip()
    b = readline().strip()
    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)))
# Original solution
# coding: utf-8

def array2d(d1, d2, init = None):
    return [[init for _ in range(d2)] for _ in range(d1)]


def solve():
    x = input().strip()
    y = input().strip()

    # dp[i][j]: x[:i], y[:j] ???LCS
    # dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1(if x[i]==y[j]))
    dp = array2d(len(x), len(y), 0)
    for i in range(len(x)):
        for j in range(len(y)):
            if i == 0 and j == 0:
                dp[0][0] = int(x[0] == y[0])
                continue
            if i > 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j > 0:
                dp[i][j] = max(dp[i][j], dp[i][j-1])
            if i > 0 and j > 0:
                cand = dp[i-1][j-1]
            else:
                cand = 0
            dp[i][j] = max(dp[i][j], cand + (x[i] == y[j]))
    return dp[-1][-1]


def main():
    cases = int(eval(input()))
    for i in range(cases):
        print((solve()))

main()

# Optimized solution
# coding: utf-8

def array2d(d1, d2, init = None):
    return [[init for _ in range(d2)] for _ in range(d1)]


def solve():
    x = input().strip()
    y = input().strip()

    # dp[i][j]: x[:i], y[:j] ???LCS
    # dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1(if x[i]==y[j]))
    dp = array2d(len(x), len(y), 0)
    dp[0][0] = int(x[0] == y[0])
    for j in range(1, len(y)):
        dp[0][j] = max(dp[0][j-1], int(x[0] == y[j]))
    for i in range(1, len(x)):
        dp[i][0] = max(dp[i-1][0], int(x[i] == y[0]))
        for j in range(1, len(y)):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if x[i] == y[j]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
    return dp[-1][-1]


def main():
    cases = int(eval(input()))
    for i in range(cases):
        print((solve()))

main()
# Original solution
import sys

def findLCS(X, Y):
    C = [[0 for i in range(1001)] for j in range(1001)]
    X, Y = " " + X, " " + Y
    m, n, maxl = len(X), len(Y), 0

    for i in range(1, m):
        for j in range(1, n):
            if X[i] == Y[j]:
                C[i][j] = C[i - 1][j - 1] + 1
            else:
                C[i][j] = max(C[i - 1][j], C[i][j - 1])
            maxl = max(maxl, C[i][j])

    return maxl

lines = sys.stdin.readlines()
N = int(lines[0])

for i in range(N):
    X = lines[2 * i + 1].strip()
    Y = lines[2 * i + 2].strip()
    print(findLCS(X, Y))

# Optimized solution
import sys

def findLCS(X, Y):
    m, n = len(X), len(Y)
    C = [0] * (n + 1)

    for i in range(m):
        tmp = C[:]
        for j in range(n):
            if X[i] == Y[j]:
                C[j + 1] = tmp[j] + 1
            elif C[j + 1] < C[j]:
                C[j + 1] = C[j]

    return C[-1]

lines = sys.stdin.readlines()
N = int(lines[0])

for i in range(N):
    X = lines[2 * i + 1].strip()
    Y = lines[2 * i + 2].strip()
    print(findLCS(X, Y))
# Original solution
def LCS():
 x = input()
 y = input()
 i = len(x)
 j = len(y)

 dsp = [[0 for col in range(j+1)] for row in range(i+1)]
 for i in range(1,i+1):
  for j in range(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 return dsp[i][j]

q = eval(input())
for i in range(q):
 print(LCS())

# Optimized solution
def LCS():
 x = input()
 y = input()
 i, j = len(x), len(y)

 dsp = [[0 for col in range(j+1)] for row in range(i+1)]
 for i in range(1,i+1):
  for j in range(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 print(dsp[i][j])

q = eval(input())
for i in range(q):
 LCS()
# Original solution
def LCS():
 x = input()
 y = input()
 i, j = len(x), len(y)

 dsp = [[0 for col in range(j+1)] for row in range(i+1)]
 for i in range(1,i+1):
  for j in range(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 print(dsp[-1][-1])

q = eval(input())
for i in range(q):
 LCS()

# Optimized solution
def LCS():
 x = input()
 y = input()
 a, b = len(x), len(y)
 dsp1 = [0 for i in range(b+1)]
 for i in range(a):
  dsp2 = dsp1+[]
  for j in range(b):
   if x[i] == y[j]:
    dsp1[j+1] = dsp2[j] + 1
   elif dsp1[j+1] < dsp1[j]:
    dsp1[j+1] = dsp1[j]
 print(max(dsp1))
  
n = eval(input())
for a in range(n):
    LCS()
# Original solution
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in range(len(x))] for j in range(len(y))]
    for i in range (1,len(y)):
        for j in range (1,len(x)):
            if x[j] == y[i]:
                a = 1
            else:
                a = 0
            c[i][j] = max(c[i][j-1],c[i-1][j],c[i-1][j-1] + a)
    return max(max(c))
n = eval(input()) 
for i in range (n): 
    x = input()
    y = input() 
    print(lcs(x,y))

# Optimized solution
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in range(len(x))] for j in range(len(y))]
    for i in range (1,len(y)):
        for j in range (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i][j-1],c[i-1][j])
    return max(max(c))
n = eval(input()) 
for i in range (n): 
    x = input()
    y = input() 
    print(lcs(x,y))
# Original solution
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in range(len(x))] for j in range(len(y))]
    for i in range (1,len(y)):
        for j in range (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i][j-1],c[i-1][j])
    return max(max(c))
n = eval(input()) 
for i in range (n): 
    x = input()
    y = input() 
    print(lcs(x,y))

# Optimized solution
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in range(len(x))] for j in range(len(y))]
    for i in range (1,len(y)):
        for j in range (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return max(max(c))
n = eval(input()) 
for i in range (n): 
    x = input()
    y = input() 
    print(lcs(x,y))
# Original solution
n = eval(input()) 
for i in range (n): 
    x = input()
    y = input() 
    
    x = " " + x
    y = " " + y
    c = [[0 for i in range(len(x))] for j in range(len(y))]
    for i in range (1,len(y)):
        for j in range (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    print(max(max(c)))

# Optimized solution
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in range(len(x))] for j in range(len(y))]
    for i in range (1,len(y)):
        for j in range (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return max(max(c))
n = eval(input()) 
for i in range (n): 
    x = input()
    y = input() 
    print(lcs(x,y))
# Original solution
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in range(len(x))] for j in range(len(y))]
    for i in range (1,len(y)):
        for j in range (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return max(max(c))
n = eval(input()) 
for i in range (n): 
    x = input()
    y = input() 
    print(lcs(x,y))

# Optimized solution
def solve():
    x = input()
    y = input()
 
    a, b = len(x), len(y)
    x1 = [0 for k in range(b+1)]
    for i in range(a):
        e1 = x[i]
        x2 = x1+[]
        for j in range(b):
            if e1 == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]
 
n = eval(input())
for i2 in range(n):
    print(solve())
# Original solution
def lcs():
    x, y = input(), input()
    x1 = [0 for k in range(len(y)+1)]
    for i in range(len(x)):
        e = x[i]
        x2 = x1 + []
        for j in range(len(y)):
            if e == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    print(max(x1))
 
n = eval(input())
for i in range(n):
    lcs()

# Optimized solution
def lcs():
    x, y = input(), input()
    b1 = [0 for k in range(len(y)+1)]
    for i in range(len(x)):
        a = x[i]
        b2 = b1 + []
        for j in range(len(y)):
            if a == y[j]:
                b1[j+1] = b2[j] + 1
            elif b1[j+1] < b1[j]:
                b1[j+1] = b1[j]
    print(max(b1))
 
n = eval(input())
for i in range(n):
    lcs()
# Original solution
# -*- coding: utf-8 -*-
def lcs(x, y):
    dp = {(0, 0): 0}
    for i in range(1, len(x) + 1):
        dp[(i, 0)] = 0
    for j in range(1, len(y) + 1):
        dp[(0, j)] = 0
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                dp[(i, j)] = dp[(i - 1, j - 1)] + 1
            else:
                dp[(i, j)] = max(dp[(i - 1, j)], dp[(i, j - 1)])

    return dp[(len(x), len(y))]


def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [[0 for j in range(m + 1)] for i in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print((lcs_sol(x, y)))



# Optimized solution
# -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            else:
                dp[j] = max(dp_prev[j], dp[j - 1])

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print((lcs_sol(x, y)))
# Original solution
# -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
            else:
                dp[j] = dp_prev[j]

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print((lcs_sol(x, y)))



# Optimized solution
# -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print((lcs_sol(x, y)))
# Original solution
# -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print((lcs_sol(x, y)))



# Optimized solution
# -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]

    return dp[m]


# if __name__ == '__main__':
import sys
q = int(sys.stdin.readline().strip())
for i in range(q):
    x = sys.stdin.readline().strip()
    y = sys.stdin.readline().strip()
    print((lcs_sol(x, y)))
# Original solution
import sys
q = int(sys.stdin.readline().strip())
for _ in range(q):
    x = sys.stdin.readline().strip()
    y = sys.stdin.readline().strip()
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
                
    print((dp[m]))



# Optimized solution
# -*- coding: utf-8 -*-
def lcs(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
            else:
                dp[j] = dp_prev[j]

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print((lcs(x, y)))