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: import sys

n=int(input())

for _ in range(n):
	x=sys.stdin.readline().rstrip('\r\n')
	y=sys.stdin.readline().rstrip('\r\n')
	
	list=[0]
	for z in y:
		for i in range(len(list)-1,-1,-1):
			tmp=x.find(z,list[i])
			if tmp+1:
				if i+1<len(list):
					list[i+1]=min(list[i+1],tmp+1)
				else:
					list.append(tmp+1)
print(len(list)-1)

Python: for _ in range(int(input())):
    x = list(input())
    y = list(input())
    lx = len(x)
    ly = len(y)
    dp = [[0] * (ly + 1) for i in range(lx + 1)]
    for i in range(lx):
        for j in range(ly):
            if x[i] == y[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])
    print(dp[-1][-1])

Python: q = int(input())
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, 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 - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    print(c[m][n])

Python: def main():
    num = int(input())
    for i in range(num):
        X = " " + input()
        Y = " " + input()
        lx = len(X)
        ly = len(Y)
        T = [0] * ly
        for j in range(1,lx):
            C = T[:]
            for k in range(1,ly):
                k1 = k-1
                if X[j] == Y[k]:
                    T[k] = C[k1] + 1
                elif C[k] < T[k1]:
                    T[k] = T[k1]
        print(T[k])

if __name__ == '__main__':
    main()

Python: # -*- coding: utf-8 -*-

import random
import sys
import os
import pprint


def LCS(s0, s1):
    m = len(s0)
    n = len(s1)

    # memo[i][j]
    memo = [[0 for j in range(n)] for i in range(m)]

    # fill at index 0
    for i in range(m):
        if s1[0] in s0[0:i+1]:
            memo[i][0] = 1
    for j in range(n):
        if s0[0] in s1[0:j+1]:
            memo[0][j] = 1

    # fill memo
    for i in range(1, m):
        for j in range(1, n):
            # same last
            if s0[i] == s1[j]:
                memo[i][j] = memo[i-1][j-1] + 1
            else:
                memo[i][j] = max(memo[i-1][j], memo[i][j-1])
    return memo[m-1][n-1]

#fd = os.open('ALDS1_10_C.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

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

Python: from collections import defaultdict
q = int(input())
for _ in range(q):
    x = input()
    y = input()
    len_x = len(x)
    len_y = len(y)
    if len_x < len_y:
        len_x, len_y = len_y, len_x
        x, y = y, x
    set_x = set(x)
    c = defaultdict(list)
    for i, s in enumerate(x):
        c[s].append(i)
    li = [0] * len_x
    for s in y:
        for i in c[s][::-1]:
            if i == 0:
                li[i] = 1
            else:
                li[i] = max(li[:i]) + 1
    print(max(li))

Python: n = int(input())
for _ in range(n):
    a, b = input(), input()
    indices = []
    for cb in b:
        bgn_idx = 0
        for i in range(len(indices) + 1):
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                if i < len(indices):
                    bgn_idx = indices[i]
                    if chr_idx < bgn_idx:
                        indices[i] = chr_idx
                else:
                    indices.append(chr_idx)
            else:
                break
    print(len(indices))

Python: def lcs(X, Y):
    m, n = len(X), len(Y)
    cost = [[1] * (n) for _ in range(m)]
    for i in range(0, m):
        if i == 0:
            continue
        for j in range(0, n):
            if j == 0:
                continue
            if X[i - 1] == Y[j - 1]:
                cost[i][j] = cost[i - 1][j - 1] + 1
            else:
                cost[i][j] = max(cost[i][j - 1], cost[i - 1][j])
    return cost[-1][-1]

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

Python: # http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=ja
# 最長共通部分文字列
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

# dp[i][j] := Sのi番目までとTのj番目までのLCS
# アルゴリズム的には正しいがTLE
def LCS(S, T):
    n = len(S)
    m = len(T)

    dp = [[0] * (m+1) for _ in range(n+1)]

    for i in range(n):
        S_i = S[i]
        for j in range(m):
            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[n][m]


def LCS2(S, T):
    L = []
    for t in T:
        t_idx = 0  # 検索開始位置
        for i, cur_idx in enumerate(L):
            chr_idx = S.find(t, t_idx) + 1
            if not chr_idx:
                break
            L[i] = min(cur_idx, chr_idx)
            t_idx = cur_idx
        else:
            chr_idx = S.find(t, t_idx) + 1
            if chr_idx:
                L.append(chr_idx)
    
    return len(L)


def main():
    q = int(readline())
    xy = read().split()

    ans = []
    for X, Y in zip(*[iter(xy)]*2):
        ans.append(LCS2(X, Y))

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Python: q = int(input())

def lcs(X, Y):
    dp = [0]*(len(Y)+1)
    
    for x in X:
        tmp = dp[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = tmp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                               
    return dp[-1]
    
for _ in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Python: import sys

sys.setrecursionlimit(1000000)


def lcd(x0, y0):
    lx, ly = len(x0), len(y0)
    memo = [[None] * ly for _ in range(lx)]

    def memoize(x, y):
        if x < 0 or y < 0:
            return 0
        if memo[x][y] is not None:
            return memo[x][y]
        result = memo[x][y] = main(x, y)
        return result

    def main(x, y):
        if x0[x] == y0[y]:
            return memoize(x - 1, y - 1) + 1
        return max(memoize(x - 1, y), memoize(x, y - 1))

    return main(lx - 1, ly - 1)


n = int(input())
while n:
    print(lcd(input(), input()))
    n -= 1