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: #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])

Python: 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")

Python: def LCS(x,y):
    n,m=len(x),len(y)
    DP=[0 for _ in range(m+1)]
    for i in range(n):
        tmp=DP[:]
        num=x[i]
        for j in range(m):
            if num==y[j]:DP[j+1]=tmp[j]+1
            elif DP[j+1]<DP[j]:DP[j+1]=DP[j]
    return DP[-1]


n=int(input())
for _ in range(n):
    print(LCS(input(),input()))

Python: e=input
a=[]
for _ in[0]*int(e()):
 X,z=e(),[]
 for y in e():
  s=i=0
  for k in z:
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k;i+=1
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 a+=[z]
print('\n'.join(map(str,map(len,a))))

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys

sys.setrecursionlimit(int(1e5))


def lcs(w1, w2):
    m, n = len(w1), len(w2)
    dp = tuple([[0] * (n + 1) for _ in range(m + 1)])
    max_l = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            max_l = max(max_l, dp[i][j])

    return max_l


def lcs_recursive(w1, w2, m, n):
    if m == 0 or n == 0:
        return 0
    elif w1[m - 1] == w2[n - 1]:
        return 1 + lcs_recursive(w1, w2, m - 1, n - 1)
    else:
        return max(
            lcs_recursive(w1, w2, m, n - 1), lcs_recursive(w1, w2, m - 1, n))


def solve():
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num

    for pair in zip(word_list[::2], word_list[1::2]):
        cw1, cw2 = map(lambda x: x.strip(), pair)
        # print(lcs(cw1, cw2))
        print(lcs_recursive(cw1, cw2, len(cw1), len(cw2)))

    return None


if __name__ == '__main__':
    solve()

Python: # coding=utf-8

def lcs(X, Y):
    global c
    m = len(X)
    n = len(Y)
    max_c = 0
    for i in range(0, m):
        for j in range(0, n):
            if X[i] == Y[j]:
                if (i == 0) or (j == 0):
                    c[i][j] = 1
                else:
                    c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
            if c[i][j] > max_c:
                max_c = c[i][j]
    return max_c

q = int(input())

for _ in range(q):
    X = list(input())
    Y = list(input())
    c = [[0 for _ in range(len(Y))] for _ in range(len(X))]
    max_c = lcs(X, Y)
    print(max_c)

Python: def answer(X, Y):
    m, n = len(X), len(Y)
    C = [[0] * (n + 1) for _ 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
            else:
                C[i][j] = max(C[i][j -1], C[i -1][j])
    return C[m][n]


if __name__ == '__main__':
    q = int(input())
    for _ in range(q):
        X = input()
        Y = input()
        print(answer(X, Y))