Go: package main

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

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

/*********************************************************************
長さmの列X_(m)と長さnの列Y_(n)の最長共通部分列LCSは、
	(1)X[m] == Y[n]ならば、X_(m-1)とY_(n-1)のLCSにX[m]を繋げたもの
	(2)X[m] != Y[n]ならば、X_(m-1)とY_(n)のLCSもしくはX_(m)とY_(n-1)のLCS
	のいずれかのうち長い方

c[m+1][n+1]：c[i][j]にX_(i)とY_(j)のLCSの長さを格納する二次元配列
*********************************************************************/

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		scanner.Scan()
		s1 := scanner.Text()
		scanner.Scan()
		s2 := scanner.Text()
		s1, s2 = " " + s1 , " " + s2
		c := make([][]int, len(s1))
		for i := range c {
			c[i] = make([]int, len(s2))
		}

		LCS := 0

		for i := 1; i < len(s1); i++ {
			for j := 1; j < len(s2); j++ {
				if s1[i] == s2[j] {
					c[i][j] = c[i-1][j-1] + 1
				} else {
					c[i][j] = max(c[i-1][j], c[i][j-1])
				}
				LCS = max(LCS, c[i][j])
			}
		}
		fmt.Println(LCS)
	}
}

Python: def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        c2 = c1[:]
        for j in range(b):
            if x[i] == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

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)]
    for x in range(NX):
        for y in range(NY):
            if X[x] == Y[y]:
                dp[x+1][y+1] = dp[x][y] + 1
            else:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y])
    print(dp[NX][NY])

Python: q = int(input())

for k in range(q):
    x = input()
    y = input()
    lcs = [0 for i in range(len(x)+1)] 
    for i in range(1,len(y) + 1):
        lcs_2 = lcs[:]
        for j in range(1,len(x) + 1):
            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[len(x)])

Python: q = int(input())
for i in range(q):
    X = input()
    Y = input()
    memo = [[0 for j in range(len(Y)+1)] for i in range(len(X)+1)]
    for i in range(1, len(X)+1):
        for j in range(1, len(Y)+1):
            x = X[:i]
            y = Y[:j]
            if x[-1] == y[-1]:
                memo[i][j] = memo[i-1][j-1] + 1
            elif memo[i-1][j] > memo[i][j-1]:
                memo[i][j] = memo[i-1][j]
            else:
                memo[i][j] = memo[i][j-1]
    print(memo[len(X)][len(Y)])

Python: import itertools
import time

c = [[0 for _ in range(1001)] for _ in range(1001)]

def make_lcs(lhs, rhs):
    llen = len(lhs)
    rlen = len(rhs)
    for l_i, r_i in itertools.product(range(llen), range(rlen)):
            c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i]) if lhs[l_i] != rhs[r_i] else c[l_i][r_i] + 1
    print(c[llen][rlen])


if __name__ == '__main__':
    # start = time.time()
    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)
    end = time.time() - start
    # print('elapsed time: {}'.format(end))

Python: def lcs(X,Y):
    Xlength = len(X)
    Ylength = len(Y)
    # print(X,Y)
    if Xlength == 0 or Ylength == 0:
        c[Xlength][Ylength] = 0
        return c[Xlength][Ylength]



    if X[Xlength -1] == Y[Ylength -1]:
        if c[Xlength-1][Ylength-1] is not None:
            c[Xlength][Ylength] = c[Xlength-1][Ylength-1]+1
        else:
            c[Xlength][Ylength] = lcs(X[:Xlength-1], Y[:Ylength-1])+1
    else:
        if c[Xlength-1][Ylength] is not None and c[Xlength][Ylength-1] is not None:
            c[Xlength][Ylength] = max(c[Xlength][Ylength-1],c[Xlength-1][Ylength])
        elif c[Xlength-1][Ylength] is not None:
            c[Xlength][Ylength] = max(lcs(X,Y[:Ylength-1]),c[Xlength-1][Ylength])
        elif c[Xlength][Ylength-1] is not None:
            c[Xlength][Ylength] = max(c[Xlength][Ylength-1],lcs(X[:Xlength-1],Y))
        else:
            c[Xlength][Ylength] = max(lcs(X,Y[:Ylength-1]),lcs(X[:Xlength-1],Y))

    return c[Xlength][Ylength]


n = int(input())
X = []
Y = []
c = [[None]*1001 for i in range(1001)]


for i in range(n):
    X.append(input())
    Y.append(input())

for i in range(n):
    # print(i)
    print(lcs(X[i],Y[i]))
    c = [[None]*1001 for i in range(1001)]

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):
        dp2 = dp1[:]
        for j in range(m):
            if x[i] == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    print(dp1[-1])

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

	if a[0]==b[0]:
		dp[0][0]=1
	for i in range(1,len(a)):
		if a[i]==b[0]:
			dp[i][0]=1
		else:
			dp[i][0]=dp[i-1][0]
	for i in range(1,len(b)):
		if a[0]==b[i]:
			dp[0][i]=1
		else:
			dp[0][i]=dp[0][i-1]
	for i in range(1, len(a)):
		for j in range(1, len(b)):
			if a[i]==b[j]:
				dp[i][j]=dp[i-1][j-1]+1
			else:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])

	print(dp[len(a)-1][len(b)-1])

Python: import sys
readline = sys.stdin.readline
for _ in range(int(input())):
    a = readline().strip()
    b = readline().strip()
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))

Python: from sys import stdin

X = [ 0 for i in range(1000) ]
Y = [ 0 for i in range(1000) ]
Z = [[0 for i in range(1000)]for i in range(1000)]

def getLCS(l) :
	xlen = len(X[l])
	ylen = len(Y[l])

	for i in range(1,xlen+1) :
		for j in range(1,ylen+1) :
			a = 1 if X[l][i-1] == Y[l][j-1] else 0
			Z[i][j] = max(Z[i-1][j-1] + a, Z[i-1][j], Z[i][j-1])

	return Z[xlen][ylen]

n = int(input())
for l in range(n) :
	X[l] = stdin.readline().strip()
	Y[l] = stdin.readline().strip()
	print(getLCS(l))

Python: for _ in[0]*int(input()):
 X,z=input(),[]
 for y in input():
  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]
 print(len(z))

Python: q = int(input())

l = []
x = ""
y = ""

for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[0] * (xLen + 1) for j in range(yLen + 1)]

    for j in range(1, yLen + 1):
        for k in range(1, xLen + 1):
            if x[k - 1] == y[j - 1]:
                l[j][k] = 1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
 
    print(l[yLen][xLen])

Python: q = int(input())

for __ in range (q):

    S1 = input()
    S2 = input()
    dp = [[0 for i in range(len(S2)+1+10)] for j in range(len(S1)+1+10)]


    for i in range (len(S1)):
        for j in range (len(S2)):
            if S1[i] == S2[j]:
                dp[i+1][j+1] = max(dp[i+1][j]+1,dp[i+1][j]+1)
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    print(dp[len(S1)][len(S2)])