Go: package main

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

var (
	nstr   func() string
	stdout *bufio.Writer
)

func init() {
	nstr = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func main() {
	defer stdout.Flush()

	n := nint()
	xList := make([]string, n)
	yList := make([]string, n)

	for i:=0;i<n ;i++  {
		xList[i] = nstr()
		yList[i] = nstr()
	}

	for i := 0; i<n	; i++  {
		fmt.Println(lcs(xList[i], yList[i]))
	}

}

func lcs(x string, y string) int{
	var m = len(x)
	var n = len(y)

	c := make([][]int, m+1)
	for i:= range c{
		c[i] = make([]int, n+1)
	}
	for i:=	1;i<=m ;i++  {
		for j:=1;j<=n ;j++  {
			if x[i-1] == y[j-1]{
				c[i][j] = c[i-1][j-1] + 1
			}else{
				c[i][j] = int(math.Max(float64(c[i-1][j]), float64(c[i][j-1])))
			}


		}
	}
	return c[m][n]

}


func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func nint64() int64 {
	i, err := strconv.ParseInt(nstr(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func nint() int {
	return int(nint64())
}

func getIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = nint()
	}
	return b
}

func getStringSlice(n int) []string {
	b := make([]string, n)
	for i := 0; i < n; i++ {
		b[i] = nstr()
	}
	return b
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

func contains(s []int, e int) bool {
	for _, a := range s {
		if a == e {
			return true
		}
	}
	return false
}

func bin(i int, prefix bool) string {
	i64 := int64(i)

	if prefix {
		return "0b" + strconv.FormatInt(i64, 2)
	} else {
		return strconv.FormatInt(i64, 2)
	}
}

func strReverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}

	return string(runes)
}

Python: 



def mk_row(data1,data2,table,row_num):
    for column in range(1,len(data2)+1):
        if(data1[row_num-1] ==data2[column-1]):
            table[row_num][column]=table[row_num-1][column-1]+1
        else:
            table[row_num][column]=max([table[row_num-1][column],table[row_num][column-1]])




n=int(input())

for loop in range(n):
    data1=input()
    data2=input()
    data1=list(data1)
    data2=list(data2)
    table=[[0]*(len(data2)+1) for i in range(len(data1)+1)]#0行、0列は空集合に対応

    for i in range(1,len(data1)+1):
        mk_row(data1,data2,table,i)
    print(table[len(data1)][len(data2)])

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]
            else:
                dp[j] = dp_prev[j]

    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: q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

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

Python: def lcs_fast(x, y):
    len_x = len(x)
    len_y = len(y)

    c = [0] * (len_y + 1)
    for i in range(len_x):
        c_prev = c[:]
        for j in range(len_y):
            if x[i] == y[j]:
                c[j+1] = c_prev[j] + 1
            elif c[j+1] < c[j]:
                c[j+1] = c[j]
    return c[-1]


if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        x = input()
        y = input()
        # print(lcs(x, y))
        print(lcs_fast(x, y))

Python: def lcs(X, Y):
    x = len(X) + 1
    y = len(Y) + 1
    c = [0 for y in range(y)]

    for i in range(1, x):
        tmp = c[:]
        for j in range(1, y):
            if X[i - 1] == Y[j - 1]:
                c[j] = tmp[j - 1] + 1
            else:
                c[j] = max(tmp[j], c[j - 1])
    return c[y - 1]

n = int(input())

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

Python: q = int(input())
alphabet =[chr(ord('a') + i) for i in range(26)]

for _ in range (q):
    S1 = list(input())
    S2 = list(input())
    S1.sort()
    S2.sort()
    count = 0
    for i in alphabet:
        temp = min(S1.count(i),S2.count(i))
        if temp !=0:
            count +=1
    print(count)

Python: from collections import defaultdict


def longest_common_subsequence(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    return dp[-1][-1]


def longest_common_subsequence2(s, t):
    dp = [0] * (len(t) + 1)
    for i in range(len(s)):
        tmp = dp[:]
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[j + 1] = tmp[j] + 1
            elif dp[j + 1] < dp[j]:
                dp[j + 1] = dp[j]
    return dp[-1]


def main():
    n = int(input())
    for _ in range(n):
        X, Y = input(), input()
        print(longest_common_subsequence2(X, Y))


if __name__ == '__main__':
    main()

Python: def lcs(x,y,l,j,k):
	if(j==0 or k==0):
		return
	if(x[j-1]==y[k-1]):
		lcs(x,y,l,j-1,k-1)
		global c
		c+=1
	else:
		if l[j-1][k]>=l[j][k-1]:
			lcs(x,y,l,j-1,k)
		else:
			lcs(x,y,l,j,k-1)

q=int(input())
c=0
for i in range(q):
	x=list(input())
	y=list(input())
	l=[[0]*(len(y)+1)]*(len(x)+1)

for j in range(1, len(x) + 1):
    for k in range(1, len(y) + 1):
        if x[j - 1] == y[k - 1]:
            a = 1
        else:
            a = 0
        l[j][k] = max(l[j-1][k-1] + a, l[j-1][k], l[j][k-1])
lcs(x,y,l,len(x),len(y))
print(c)

Python: for _ in[0]*int(input()):
 X,Y=' '+input(),' '+input();m,n=len(X),len(Y);c=[[0]*n for _ in[0]*m]
 for i in range(1,m):
  for j in range(1,n):c[i][j]=1+c[i-1][j-1]if X[i]==Y[j]else c[i-1][j]if c[i-1][j]>c[i][j-1]else c[i][j-1]
 print(c[m-1][n-1])

Python: q = int(input())

for k in range(q):
    x = input()
    y = input()
    ex = len(x)+1
    lcs = [0] *ex 
    for i in range(1,len(y) + 1):
        lcs_2 = lcs[:]
        for j in range(1,ex):
            if x[j-1] == y[i-1]:
                lcs[j] = lcs_2[j-1] + 1  
            elif lcs[j] < lcs[j-1]:
                lcs[j] = lcs[j-1]
    print(lcs[-1])

Python: def lcs(s, t):
  slen = len(s)
  tlen = len(t)
  dp = [0] * (slen + 1)
  for i in range(slen + 1):
    dp[i] = [0] * (tlen + 1)

  for i in range(1, slen + 1):
    for j in range(1, tlen + 1):
      if s[i-1] == t[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i][j-1], dp[i-1][j])

  return dp[slen][tlen]

n = int(raw_input())

for i in range(n):
  x = raw_input()
  y = raw_input()
  print(lcs(x, y))