Go: package main

import (
	. "fmt"
    "math"
)

// func init() { Println("----------------------------------------") }

func main() {
    const L_MAX = 1003

	var q int
	Scanf("%d", &q)
	X := make([]string, 0, 150)
	Y := make([]string, 0, 150)
	for i := 0; i < 2 * q; i++ {
	    var tmp string
	    Scanf("%s", &tmp)

	    if i % 2 == 0 {
	        X = append(X, tmp)
	    } else {
	        Y = append(Y, tmp)
	    }
	}

    for i := 0; i < q; i++ {
        dp := make([][]int, L_MAX)
        for k, _ := range dp {
            dp[k] = make([]int, L_MAX)
        }

        x, y := X[i], Y[i]

        // init
        isXFound := false
        for c := 0; c < len(x); c++ {
            if isXFound || y[0] == x[c] {
                dp[0][c] = 1
                isXFound = true
            }
        }
        isYFound := false
        for r := 0; r < len(y); r++ {
            if isYFound || x[0] == y[r] {
                dp[r][0] = 1
                isYFound = true
            }
        }

        for r := 1; r < len(y); r++ {
            for c := 1; c < len(x); c++ {
                // dp[r][c]
                if x[c] == y[r] {
                    dp[r][c] = int(math.Max(float64(dp[r - 1][c - 1] + 1), float64(dp[r][c])))
                }

                dp[r][c] = int(math.Max(float64(dp[r][c]), math.Max(float64(dp[r - 1][c]), float64(dp[r][c - 1]))))
            }
        }
        Println(dp[len(y) - 1][len(x) - 1])

        // LCSも求めておく
        // ans := ""
        // r, c := len(y) - 1, len(x) - 1
        // for r >= 0 && c >= 0 {
        //     if y[r] == x[c] {
        //         ans = string(x[c]) + ans
        //         r--
        //         c--
        //     } else {
        //         if dp[r - 1][c] > dp[r][c - 1] {
        //             r--
        //         } else {
        //             c--
        //         }
        //     }
        // }
        // Println(ans)
    }
}

Python: n = int(input())
xs = []
ys = []
for _ in range(n):
    x = input()
    y = input()
    xs.append(x)
    ys.append(y)

for i in range(n):
    a, b = xs[i], ys[i]
    L = []
    for bk in b:
        bgn_idx = 0
        for j, cur_idx in enumerate(L):
            chr_idx = a.find(bk, bgn_idx) + 1
            if not chr_idx:
                break
            L[j] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(bk, bgn_idx) + 1
            if chr_idx:
                L.append(chr_idx)
    print(len(L))

Python: q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    d = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[i+1][j+1] = d[i][j]+1
            else:
                d[i+1][j+1] = max(d[i+1][j],d[i][j+1])
    print(d[n][m])

Python: from bisect import bisect_left
q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    p = []
    for i, c in enumerate(s1):
        s = 0
        while True:
            j = s2[s:].find(c)
            if j == -1:
                break
            p.append((i, s+j))
            s += j+1

    lis = []
    for _, y in sorted(p, key=lambda x: (x[0], -x[1])):
        i = bisect_left(lis, y)
        if len(lis) <= i:
            lis.append(y)
        else:
            lis[i] = y
    print(len(lis))

Python: n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    #array = [[0]*nb for i in range(na)]
    array = [[0 for i in range(nb)] for j in range(na)]
    for i in range(na):
        for j in range(nb):
            c = 0
            if i==0:
                if a[i]==b[j]:
                    array[i][j]=1
            elif j==0:
                if a[i]==b[j]:
                    array[i][j]=1
            else:
                if a[i] == b[j]:
                    c = 1
                array[i][j] = max(
                    array[i-1][j],
                    array[i][j-1],
                    array[i-1][j-1]+c)
    print(array[na-1][nb-1])

Python: from collections import defaultdict
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)
    def g(li, a):
        for i in li:
            if i >= a:
                return i
        return -1
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = g(c[s2_k], bgn_idx)
            if chr_idx == INF:
                continue
            dp[i] = min(cur_idx, chr_idx + 1)
            bgn_idx = cur_idx
        else:
            chr_idx = g(c[s2_k], bgn_idx)
            if chr_idx != INF:
                dp.append(chr_idx + 1)
    return len(dp)
def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))
solve()

Python: #JOI
def main():
    X=input()
    Y=input()
    dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
    for x in range(len(X)):
        for y in range(len(Y)):
            now=0
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            idx=Y[:y+1].rfind(X[x])
            if idx!=-1:
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            idx=X[:x+1].rfind(Y[y])
            if idx!=-1:
                dp[x][y]=max(dp[idx-1][y-1]+1,dp[x][y])
    print(dp[len(X)-1][len(Y)-1])
for i in range(int(input())):
    main()

Python: def lcs(X, Y):
    if not len(X) or not len(Y):
        return 0
    if X[-1] == Y[-1]:
        return 1 + lcs(X[:-1], Y[:-1])
    else:
        return max(lcs(X[:-1], Y), lcs(X, Y[:-1]))

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Python: m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0]*(len(str2)+1)
    for char1 in str1:
        A_copy = A[:]
        for j,char2 in enumerate(str2):
            if(char1==char2):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])

Python: q = int(input())
for _ in range(q):
    X = input()
    Y = input()
    NX = len(X)
    NY = len(Y)
    dp = [[0] * (NY+1) for _ in range(NX+1)]
    jx = [0 for _ in range(NX)]
    jy = [0 for _ in range(NY)]
    for x in range(NX):
        for y in range(NY):
            if jx[x] == 0 and jy[y] == 0 and X[x] == Y[y]:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y]) + 1
                jx[x] = 1
                jy[y] = 1
            else:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y])

    print(dp[NX][NY])

Python: n=int(input())
al=[]
bl=[]
for i in range(n):
	al.append(list(input()))
	bl.append(list(input()))

for i in range(n):
	a=al.pop(0)
	b=bl.pop(0)
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	for i in range(len(a)):
		for j in range(len(b)):
			if i==0:
				if j==0:
					if a[i]==b[j]:
						dp[i][j]=1
					else:
						dp[i][j]=0
				elif a[i]==b[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i][j-1]
			elif j==0:
				if a[i]==b[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i-1][j]

			elif a[i]!=b[j]:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
			else:
				dp[i][j]=dp[i-1][j-1]+1

	print(dp[len(a)-1][len(b)-1])

Python: #dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    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]
    print(array[na][nb])