Go: package main

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

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func main(){
	var n int 
	fmt.Scan(&n)
	dp := make([][]int, 1003)
	for i:=0; i<1003; i++ {
		dp[i] = make([]int, 1003)
	}
	input_lines := scanStringLine(2*n)
	for i:=0; i<n; i++ {
		S, T := input_lines[2*i], input_lines[2*i+1]
		lenS, lenT := len(S), len(T)
		for i:=1; i<lenS+1; i++ {
			for j:=1; j<lenT+1; j++ {
				if S[i-1] == T[j-1] {
					dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
				} else {
					dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
				}
			}
		}
		fmt.Println(dp[lenS][lenT])
	}
}

Python: def lcs(str1,str2):
    f=[[0 for i in range(len(str2)+1)]for j in range(len(str1)+1)]
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
           if str1[i-1]==str2[j-1]:
              f[i][j]=f[i-1][j-1]+1
           else:
              f[i][j]=max(f[i-1][j],f[i][j-1])
    return f[-1][-1]
               

N=int(input())
for i in range(N):
    x=input()
    y=input()
    print(lcs(x,y))

Python: from typing import List


def make_lcs(lhs, rhs):
    pass


class stub():
    def __init__(self):
        self.fin = open('task.txt')

    def stub_input(self):
        return self.fin.readline()


# _stub = stub()
# input = _stub.stub_input


def make_lcs(lhs: List[str], rhs: List[str]):
    c = [[0 for _ in range(len(rhs) + 1)] for _ in range(len(lhs) + 1)]
    for l_i in range(len(lhs)):
        for r_i in range(len(rhs)):
            if lhs[l_i] == rhs[r_i]:
                c[l_i + 1][r_i + 1] = c[l_i][r_i] + 1
            else:
                c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i])
    print(c[-1][-1])


if __name__ == '__main__':
    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)

Python: def longest_common(x, y):
    cost = [0]
    for c in y:
        for i in range(len(cost) -1, -1, -1):
            index = x.find(c, cost[i]) + 1
            if index:
                if i + 1 < len(cost):
                    cost[i + 1] = min(cost[i + 1], index)
                else:
                    cost.append(index)
    return len(cost)  - 1
            

n = int(input())
for _ in range(n):
    x = input()
    y = input()
    print(longest_common(x, y))

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

    for i in X:
        tmp = c[:]
        for ji, yc in enumerate(Y):
            j = ji + 1
            if i == yc:
                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 = sys.stdin.readline()[:-1]
    Y = sys.stdin.readline()[:-1]
    print(lcs(X, Y))

Python: def search(X, Y):
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                dp[x][y] = dp[x-1][y-1] + 1
            elif dp[x-1][y] > dp[x][y-1]:
                dp[x][y] = dp[x-1][y]
            else:
                dp[x][y] = dp[x][y-1]
    return dp[-1][-1]

N = int(input())
for i in range(N):
    X = input()
    Y = input()
    print(search(X, Y))

Python: n=int(input())
ans=[]
for k in range(n):
    s1=input()
    s2=input()
    dp=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            if s1[i-1]==s2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])


    ans.append(dp[len(s1)][len(s2)])
for a in ans:
    print(a)

Python: def LCS(str1,str2):
    A = [0 for _ in range(len(str2)+1)]
    for i in range(len(str1)):
        A_copy = A[:]
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    LCS(str1,str2)

Python: import itertools

q = int(input())
for a in range(q):
    X = input()
    Y = input()
    cost = [0]
    for c in Y:
        for i in range(len(cost) - 1, -1, -1):
            index = X.find(c, cost[i]) + 1
            if index:
                if i + 1 < len(cost):
                    cost[i + 1] = min(cost[i + 1], index)
                else:
                    cost.append(index)
    print(len(cost) - 1)

Python: for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0 for y in range(len(Y)+1)] for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                dp[x][y] = dp[x-1][y-1] + 1
            else:
                dp[x][y] = max(dp[x-1][y], dp[x][y-1])
    print(dp[-1][-1])

Python: def lcs_hs(s1, s2):
    from bisect import bisect_left

    s2 = s2[::-1]
    lis, result = [], 0
    append = lis.append

    for c in s1:
        i = s2.find(c)+1
        while i:
            j = bisect_left(lis, -i)
            if j >= result:
                append(-i)
                result += 1
            else:
                lis[j] = -i
            i = s2.find(c, i)+1

    return result


print(*(lcs_hs(input(), input()) for _ in [0]*int(input())), sep="\n")

Python: #dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0 for i in range(nb+1)] for j in range(na+1)]
    for i in range(1,na+1):
        for j in range(1,nb+1):
            c = 0
            if a[i-1] == b[j-1]:
                array[i][j]=array[i-1][j-1]+1
            else:
                array[i][j] = max(array[i-1][j],array[i][j-1])
    print(array[na][nb])

Python: n=int(input())
x=[0 for i in range(n)]
y=[0 for i in range(n)]
for i in range(n):
    x[i]=input()
    y[i]=input()

for i in range(n):
    X=list(x[i])
    Y=list(y[i])
    a=[int(0) for i in range(len(X))]
    for j in range(len(X)):
        b=-1
        for l in range(j,len(X)):
            for k in range(len(Y)):
                if X[l]==Y[k] and b<k:
                    b=k
                    a[j]+=1
                    break
                
    print(max(a))