Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const N = 1001

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func lcs(x, y string) int {
	var c [N][N]int
	m := len(x)
	n := len(y)
	var maxl int

	x = " " + x
	y = " " + y

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			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
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())

	var out bytes.Buffer
	for i := 0; i < q; i++ {
		sc.Scan()
		s1 := sc.Text()
		sc.Scan()
		s2 := sc.Text()
		out.WriteString(fmt.Sprintf("%d\n", lcs(s1, s2)))
	}
	return strings.TrimRight(out.String(), "\n")
}

func main() {
	fmt.Println(answer(os.Stdin))
}

Python: def make_lcs(lhs , rhs):
    c = [[0 for _ in range(len(rhs) + 1)] for _ in range(len(lhs) + 1)]
    for l_i in range(len(lhs)):
        for r_i in range(len(rhs)):
            if lhs[l_i] == rhs[r_i]:
                c[l_i + 1][r_i + 1] = c[l_i][r_i] + 1
            else:
                c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i])
    print(c[-1][-1])


if __name__ == '__main__':
    n = int(input())
    for _ in range(n):
        lhs = [i for i in input().rstrip()]
        rhs = [i for i in input().rstrip()]
        make_lcs(lhs, rhs)

Python: #Longest Common Subsequence
#?????????

def lastindex(a,x):
    #????????????a??????????????????????????????x??????????????????????????????????????????1???????????????????????????x????????¨???????????¨??????-1????????????
    try:
        return len(a)-a[::-1].index(x)-2
    except:
        return(-1)

'''
X={x1,x2,...xm}
Y={y1,y2,...yn}????????????

Xi={x1,x2,...xi}(1<=i<=m)
Yj={y1,y2,...yj}(1<=j<=n)
Z(i,j)=Xi??¨Yj???????????±?????¨???????????????
??¨?????????????????¨???

Zi,j=max{
	Z(lastindex(Xi,yj),j-1)+1
	Z(i-1,lastindex(Yj,xi))+1
	Z(i-1,j)
	Z(i,j-1)
}
??¨?????????
??¢??°lastindex??§???(Zi,j????¨????????????¨????????§?????????)??????1??????????????????????????????????????????lastindex(a,x)???0?????¨??????lastindex(a,i)-1=-1??¨?????£???????????????Z[lastindex(a,x)-1][...]?????¨?????\?????????????????£?????????????????????
a?????????x????????¨???????????????????????????-1??¨???????????¨??§?????????????????°???????????§?????¨??????-1?????????????????????
'''

#????????????????????°????????§?????£???????????????AOJ????????????????????¨??????????????????X??¨Y????\???????????????¨??????TLE??¨?????£???????????£??????

q=int(input())


for repeat in range(q):
    X=input()
    Y=input()
    lenX=len(X)
    lenY=len(Y)
    Z=[[0 for i in range(lenY)] for i in range(lenX)]

    if X[0]==Y[0]:
        Z[0][0]=1
    
    for i in range(1,lenY):
        if Z[0][i-1]==1:
            Z[0][i]=1
        else:
            if Y[i]==X[0]:
                Z[0][i]=1

    for j in range(lenX):
        if Z[j-1][0]==1:
            Z[j][0]=1
        else:
            if X[j]==Y[0]:
                Z[j][0]=1


    for i in range(1,lenX):
        for j in range(1,lenY):
            x=lastindex(X[:i+1:],Y[j])
            y=lastindex(Y[:j+1:],X[i])

            if x!=-1 and y!=-1:
                Z[i][j]=max(Z[x][j-1],Z[i-1][y])+1
            elif x!=-1:
                Z[i][j]=Z[x][j-1]+1
            elif y!=-1:
                Z[i][j]=Z[i-1][y]+1

            Z[i][j]=max(Z[i][j],Z[i-1][j],Z[i][j-1])

    print(Z[-1][-1])

Python: # -*- coding: utf-8 -*-
import functools


def lcs(x, y):
    n = len(x)
    m = len(y)
    return rec(x, y, n, m)


@functools.lru_cache(maxsize=None)
def rec(x, y, i, j):
    if i == 0 or j == 0:
        return 0
    elif x[i - 1] == y[j - 1]:
        return rec(x, y, i - 1, j - 1) + 1
    else:
        return max(rec(x, y, i, j - 1), rec(x, y, i - 1, j))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**7)
    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))

Python: import sys
def lcs(X, Y):
    indices = [0]
    for c in Y:
        for i in range(len(indices) - 1, -1, -1):
            tmp = X.find(c, indices[i])
            if tmp + 1:
                if i + 1 < len(indices):
                    indices[i + 1] = min(indices[i + 1], tmp + 1)
                else:
                    indices.append(tmp + 1)
    return len(indices) - 1

q = int(input())
for i in range(q):
    X = sys.stdin.readline().rstrip('\r\n')
    Y = sys.stdin.readline().rstrip('\r\n')
    print(lcs(X, Y))

Python: import sys
from functools import lru_cache

sys.setrecursionlimit(3 * 1000)

@lru_cache(maxsize=None)
def lcs_rec(i, j):
    if i == 0 or j == 0:
        return 0

    if X[i - 1] == Y[j - 1]:
        return lcs_rec(i - 1, j - 1) + 1
    else:
        return max(lcs_rec(i - 1, j), lcs_rec(i, j - 1))

q = int(input())

for i in range(q):
    X = input()
    Y = input()

    ans = lcs_rec(len(X), len(Y))

    print(ans)

Python: # -*- 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))

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

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

    return dp[m][n]


def main():
    q = int(input())

    for i in range(q):
        x, y = input(), input()
        print(lcs(x, y))


if __name__ == '__main__':
    main()

Python: n=int(input())
ans=[]
for k in range(n):
    s1=input()
    s2=input()
    dp=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            if s1[i-1]==s2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])


    ans.append(dp[len(s1+1)][len(s2+1)])
for a in ans:
    print(a)

Python: q = int(input())

l = []
x = ""
y = ""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex < 0 or yIndex < 0:
        return 0
    elif l[yIndex][xIndex] != -1:
        return l[yIndex][xIndex]
    elif x[xIndex] == y[yIndex]:
        return 1 + lcs(yIndex - 1, xIndex - 1)
    else:
        return max(lcs(yIndex, xIndex - 1), lcs(yIndex - 1, xIndex))

for i in range(q):
    x = input()
    y = input()

    l = [[-1] * len(x) for j in range(len(y))]

    for j in range(len(y)):
        for k in range(len(x)):
            l[j][k] = lcs(j, k)

    print(l[len(y)- 1][len(x) - 1])

Python: q = int(input())
for i in range(q):
    x = input()
    y = input()
    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]
    print(dp1[-1])