Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	for i := 0; i < n; i++ {
		x := getNextString(scanner)
		y := getNextString(scanner)

		fmt.Fprintln(writer, lcs(x, y))
	}

	writer.Flush()
}

func lcs(x, y string) int {
	lx := len(x)
	ly := len(y)
	dp := make([][]int, lx+1)
	for i := 0; i <= lx; i++ {
		dp[i] = make([]int, ly+1)
	}
	for i := 0; i < lx; i++ {
		for ii := 0; ii < ly; ii++ {
			if x[i] == y[ii] {
				dp[i+1][ii+1] = dp[i][ii] + 1
				continue
			}
			dp[i+1][ii+1] = dp[i][ii+1]
			if dp[i+1][ii] > dp[i+1][ii+1] {
				dp[i+1][ii+1] = dp[i+1][ii]
			}
		}
	}
	return dp[lx][ly]
}

Python: def main():
    n = int(input())
    for i 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])
if __name__ == "__main__":
    main()

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

import random
import sys
import os
import pprint


def LCS(s0, s1):
    # print(s0)
    # print(s1)
    m = len(s0)
    n = len(s1)

    # memo[i][j]
    memo = [[0] * n for i in range(m)]
    # pprint.pprint(memo)

    # fill at index 0
    index = s0.find(s1[0])
    if index != -1:
        for i in range(index, m):
            memo[i][0] = 1

    index = s1.find(s0[0])
    if index != -1:
        for j in range(index, n):
            memo[0][j] = 1

    """
    for i in range(m):
        if s1[0] in s0[0:i+1]:
            memo[i][0] = 1
    for j in range(n):
        if s0[0] in s1[0:j+1]:
            memo[0][j] = 1
    """

    # fill memo
    for i in range(1, m):
        for j in range(1, n):
            # same last
            if s0[i] == s1[j]:
                memo[i][j] = memo[i-1][j-1] + 1
            else:
                memo[i][j] = max(memo[i-1][j], memo[i][j-1])
    return memo[m-1][n-1]


"""
def LCS_better(s0, s1):
    dp = [0] * len(s1) # cost use till j
    for c in s0:
        tmp = dp[:]
        for j in range(len(s1)):
            if c == s1[j]:
                dp[j + 1] = tmp[j] + 1
            elif dp[j + 1] < dp[j]:
                dp[j + 1] = dp[j]
    return dp[-1]
"""

#fd = os.open('ALDS1_10_C.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

n = int(input())
for _ in range(n):
    s0 = input()
    s1 = input()
    l = LCS(s0, s1)
    #l2 = LCS_better(s0, s1)
    print(l)

Python: def lcs(x, y):
    L = []
    for y_k in y:
        si = 0
        for i, cri in enumerate(L):
            chi = x.find(y_k, si) + 1
            if not chi:
                break
            L[i] = min(cri, chi)
            si = cri
        else:
            chi = x.find(y_k, si) + 1
            if chi:
                L.append(chi)
    return len(L)


if __name__ == "__main__":
    N = int(input())
    ans = []
    for _ in range(N):
        X = input()
        Y = input()
        print(lcs(X, Y))

Python: from sys import stdin
input = stdin.readline

N = 1000

def lcs(X, Y):
    c = [[0]*(N+1) for _ in range(N+1)]
    maxl = 0
    X = ' ' + X # 1オリジンにする
    Y = ' ' + Y
    pre_row = c[0]
    for i, x in enumerate(X):
        if i == 0:
            continue
        row = c[i]
        for j, y in enumerate(Y):
            if j == 0:
                continue
            if x == y:
                value = pre_row[j-1] + 1
                row[j] = value
                if maxl < value: # maxlの更新はこの時しか起こらない
                    maxl = value
            else:
                pre_row_j = pre_row[j]
                row_j_1 = row[j-1]
                value = row_j_1
                if pre_row_j > row_j_1:
                    value = pre_row_j # max関数だと、とても遅い
                row[j] = value
        pre_row = row # 今の列が次の列にとって一つ前の列になる

    return maxl

n = int(input())
for _ in range(n):
    s1 = input()[:-1]
    s2 = input()[:-1]
    print(lcs(s1, s2))

Python: import sys

def lcm(c,i, j):
    if c[i][j]>0: return c[i][j]        
    if i==0 or j==0:
        return 0
    elif x[i]==y[j]:
        c[i][j] = lcm(c,i-1,j-1)+1
        return c[i][j]
    else:
        c[i][j] = max(lcm(c,i,j-1), lcm(c,i-1,j))
        return c[i][j]

for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline()
    y = sys.stdin.readline()
    c = [[0 for _ in range(len(x)+2)] for _ in range(len(y)+2)] 
    print(lcm(c,len(x)-1,len(y)-1))

Python: q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    ans.append(c[-1])

print(*ans, sep="\n")