Go: package main

/*
最長共通部分列
*/

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

func larger(l, r int) int {
	if l > r {
		return l
	}
	return r
}

var memo [1001][1001]int

func countLCS(x, y string) int {
	x = " " + x
	y = " " + y
	max := 0
	for xi := 1; xi < len(x); xi++ {
		for yi := 1; yi < len(y); yi++ {
			if x[xi] == y[yi] {
				memo[xi][yi] = memo[xi-1][yi-1] + 1
			} else {
				memo[xi][yi] = larger(memo[xi-1][yi], memo[xi][yi-1])
			}
			max = larger(max, memo[xi][yi])
		}
	}
	return max
}

func main() {
	scanner := makeScanner(1024)
	q := eGetInt(scanner)
	for i := 0; i < q; i++ {
		x := eGetLine(scanner)
		y := eGetLine(scanner)
		fmt.Println(countLCS(x, y))
	}
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}

type ints []int

func (s ints) String() string {
	var buf bytes.Buffer
	buf.WriteString("[")
	sep := ""
	for _, v := range s {
		buf.WriteString(fmt.Sprintf("%s%d", sep, v))
		sep = ", "
	}
	buf.WriteString("]")
	return buf.String()
}

func reverse(a ints) ints {
	r := make(ints, len(a))
	for i := 0; i < len(a); i++ {
		r[i] = a[len(a)-1-i]
	}
	return r
}
func max(a ints) (int, bool) {
	if len(a) == 0 {
		return 0, false
	}
	m := a[0]
	for _, e := range a {
		if e > m {
			m = e
		}
	}
	return m, true
}
func min(a []int) int {
	m := a[0]
	for _, v := range a {
		if v < m {
			m = v
		}
	}
	return m
}

func sum(a ints) int {
	if len(a) == 0 {
		return 0
	}
	sum := 0
	for _, e := range a {
		sum += e
	}
	return sum
}
func find(n int, a ints) int {
	for i, v := range a {
		if n == v {
			return i
		}
	}
	return -1
}

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

Python: from itertools import chain
from collections import deque
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] == y[j]:
                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 = deque(stdin.readlines())
ret = []
for i in range(n):
    s1 = strs.popleft().rstrip()
    s2 = strs.popleft().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())
    x=len(a)+1
    y=len(b)+1

    r=[[0 for j in range(y)]for i in range(x)]

    for j in range(1,x):
        for k in range(1,y):
            if r[j-1][k]>r[j][k-1]:
                c=r[j-1][k]
            else:
                c=r[j][k-1]
            if a[j-1]==b[k-1]:
                if r[j-1][k-1]+1>c:
                    c=r[j-1][k-1]+1
            
            r[j][k]=c    
    print(r[x-1][y-1])

Python: import sys
from functools import lru_cache

sys.setrecursionlimit(3 * 1000)

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: def calc_lcs(X, Y):
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = [[0 for _ in range(1000+1)] for i in range(1000+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            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] = c[i][j - 1]
            max_lcs = max(max_lcs, c[i][j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # X = 'abcbdab'
    # Y = 'bdcaba'

    for _ in range(num):
        X = input()
        Y = input()

        # ???????????????
        result = calc_lcs(X, Y)

        # ???????????¨???
        print(result)

Python: import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]



n = int(input())
s = []
for line in sys.stdin:
    s.append(line.strip())
for i in range(0, 2*n, 2):
    print(len_lcs(s[i], s[i+1]))

Python: import sys
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0 for i 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]:
                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 str(c[m][n])

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: q = int(input())
X = ""
Y = ""
memo = [[]]

def LCS(x, y):
    if (x < 0) or (y < 0):
        return 0
    elif memo[x][y] != -1:
        return memo[x][y]
    else:
        memo[x][y] = max(LCS(x-1,y), LCS(x,y-1), LCS(x-1, y-1)+int(X[x] == Y[y]))
        return memo[x][y]

for c in range(q):
    X = input()
    Y = input()
    memo = [[-1 for j in range(len(Y))] for i in range(len(X))]
    print(LCS(len(X)-1, len(Y)-1))

Python: q = int(input())
for _ in range(q):
    X = input()
    Y = input()

    dp = [[0 for _ in range(len(Y) + 1)] for _ in range(len(X) + 1)]
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i] == Y[j]:
                dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    print(dp[len(X)][len(Y)])