Go: package main

import (
	. "fmt"
    "math"
)

// func init() { Println("----------------------------------------") }

func main() {
    const L_MAX = 1003

	var q int
	Scanf("%d", &q)
	X := make([]string, 0, 150)
	Y := make([]string, 0, 150)
	for i := 0; i < 2 * q; i++ {
	    var tmp string
	    Scanf("%s", &tmp)

	    if i % 2 == 0 {
	        X = append(X, tmp)
	    } else {
	        Y = append(Y, tmp)
	    }
	}

    for i := 0; i < q; i++ {
        dp := make([][]int, L_MAX)
        for k, _ := range dp {
            dp[k] = make([]int, L_MAX)
        }

        x, y := X[i], Y[i]

        // init
        isXFound := false
        for c := 0; c < len(x); c++ {
            if isXFound || y[0] == x[c] {
                dp[0][c] = 1
                isXFound = true
            }
        }
        isYFound := false
        for r := 0; r < len(y); r++ {
            if isYFound || x[0] == y[r] {
                dp[r][0] = 1
                isYFound = true
            }
        }

        for r := 1; r < len(y); r++ {
            for c := 1; c < len(x); c++ {
                // dp[r][c]
                if x[c] == y[r] {
                    dp[r][c] = int(math.Max(float64(dp[r - 1][c - 1] + 1), float64(dp[r][c])))
                }

                dp[r][c] = int(math.Max(float64(dp[r][c]), math.Max(float64(dp[r - 1][c]), float64(dp[r][c - 1]))))
            }
        }
        Println(dp[len(y) - 1][len(x) - 1])

        // LCSも求めておく
        // ans := ""
        // r, c := len(y) - 1, len(x) - 1
        // for r >= 0 && c >= 0 {
        //     if y[r] == x[c] {
        //         ans = string(x[c]) + ans
        //         r--
        //         c--
        //     } else {
        //         if dp[r - 1][c] > dp[r][c - 1] {
        //             r--
        //         } else {
        //             c--
        //         }
        //     }
        // }
        // Println(ans)
    }
}

Python: def Ics(X, Y):
    m = len(X)
    n = len(Y)
    maxl = 0
    for i in range(m + 1):
        c[i][0] = 0
    for j in range(1, n + 1):
        c[0][j] = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if(X[i] == Y[j]):
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i][j - 1], c[i - 1][j])
            maxl = max(maxl, c[i][j])
    return maxl

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(lcs(s1, s2))
print(*t, sep="\n")

Python: def calc(x,y):
    i = len(x)
    j = len(y)
    if d[i][j]:
        return d[i][j]
    else:
        if i == 1:
            if x in y:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        elif j == 1:
            if y in x:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        else:
            if x[-1] == y[-1]:
                tmp = max(calc(x[:-1],y[:-1])+1,calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
            else:
                tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[None for _ in range(len(y)+1)] for _ in range(len(x)+1)]
    print(calc(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]

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

Python: n = int(input())

# result = []

memo = {}


def search(s1, s2):

    if (s1, s2) in memo:
        return memo[(s1, s2)]

    total = [0]

    if s1:
        s1_head, s1_body = s1[0], s1[1:]
        for idx2, s2_tgt in enumerate(s2):
            if s1_head == s2_tgt:
                total.append(1+search(s1_body, s2[idx2+1:]))

    if s2:
        s2_head, s2_body = s2[0], s2[1:]
        for idx1, s1_tgt in enumerate(s1):
            if s2_head == s1_tgt:
                total.append(1+search(s1[idx1+1:], s2_body))

    if s1 and s2:
        total.append(search(s1[1:], s2[1:]))

    memo[(s1, s2)] = max(total)
    return max(total)
    # print(rs)


for _ in range(n):
    s1 = input()
    s2 = input()
    result = search(s1, s2)
    print(result)

Python: import bisect


def LCS(S, T):
    N = len(S)
    M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    for i, s in enumerate(S, start=1):
        for j, t in enumerate(T, start=1):
            if s == t:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[N][M]


def LCS_HTKB(S, T):
    T = T[::-1]
    memo = []

    for s in S:
        i = T.find(s) + 1
        while i:
            j = bisect.bisect_left(memo, -i)
            if j >= len(memo):
                memo.append(-i)
            else:
                memo[j] = -i
            i = T.find(s, i) + 1
    return len(memo)


if __name__ == "__main__":
    Q = int(input())
    ans = []
    for _ in range(Q):
        ans.append(LCS_HTKB(input(), input()))
    print(*ans, sep="\n")

Python: def lcs(X, Y):
    global c
    m, n = len(X), len(Y)
    c = [[0 for i in range(n+1)] for j 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-1][j], c[i][j-1])
    return c[m][n]

def lcs_improved(X, Y):
    hist = [0] # yの文字cまでを見た時に, hist[i]以降の文字列において, 共通文字のうち, 一番小さいindexのもの
    for c in Y:
        for i in range(len(hist)-1, -1, -1):
            next_match_i = X.find(c, hist[i])+1
            if next_match_i:
                if i+1 < len(hist):
                    hist[i+1] = min(hist[i+1], next_match_i)
                else:
                    hist.append(next_match_i)
    return len(hist)-1

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs_improved(X, Y))

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

output:
4
3
2

"""
import sys


def lcs(w1, w2):
    m, n = len(w1), len(w2)
    dp = [[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 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))
        # l1, l2 = len(cw1), len(cw2)
        # print(lcs_recursive(cw1, cw2, l1, l2))

    return


if __name__ == '__main__':
    solve()

Python: def lcs(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, m+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])

    return dp[n][m]

def solve():
    N = int(input())
    for _ in range(N):
        a = input()
        b = input()
        print(lcs(a, b))

if __name__ == '__main__':
    solve()