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(){
	buf := make([]byte, 0)
    sc.Buffer(buf, 1000000009)
	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] = dp[i-1][j-1]+1
				} else if S[i-1] != T[j-1] && dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
				// 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(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == 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: def ask(X,Y):

 a=len(X)
 b=len(Y)
 Z=[]
 c=0
 for n in range(a):
  z=0
  for i in range(n,a):
   for j in range(c,b):
    if(X[i]==Y[j]):
     z+=1
     c=j
     break
  Z.append(z)

 Z.sort();
 return Z[a-1]


q=int(input())
Z=[]
for p in range(q):
 x=input()
 X=list(x)
 y=input()
 Y=list(y)
 z=ask(X,Y)
 Z.append(z)

for p in range(q):
 print(Z[p])

Python: #!/usr/bin/env python3
import sys
sys.setrecursionlimit(15000)
n = int(sys.stdin.readline())

def lcs(X,Y):
  n_y = len(Y)
  n_x = len(X)
  #dp = [[0]*(n_x+1) for _ in range(n_y+1)]
  dp = [0]*(n_x+1)
  for i_y in range(n_y):
    ndp = dp.copy()
    for i_x in range(n_x):
      if X[i_x] == Y[i_y]:
        #dp[i_y+1][i_x+1] = dp[i_y][i_x] + 1
        ndp[i_x+1] = dp[i_x] + 1
      elif dp[i_x+1] < ndp[i_x]:
        #dp[i_y+1][i_x+1] = max(dp[i_y+1][i_x],dp[i_y][i_x+1])
        ndp[i_x+1] = ndp[i_x]
    dp = ndp
    #print(dp)
    #return(dp[-1][-1])
  return(dp[-1])

ret = []
inp = sys.stdin.readlines()
for i in range(n):
  X = inp[2*i].rstrip()#[:-1]#input()
  Y = inp[2*i+1].rstrip()#[:-1]#input()
  ret.append(lcs(X,Y))
  #print

print(*ret,sep="\n")

Python: n = int(input())

def lcs(x, y):
    xlen = len(x)
    ylen = len(y)
    if xlen == 0 or ylen == 0:
        return 0
    elif x[xlen-1] == y[ylen-1]:
        return lcs(x[:-1], y[:-1]) + 1
    else:
        return max(lcs(x, y[:-1]), lcs(x[:-1], y))

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

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

q=int(input())
A=[0 for i in range(q)]
for i in range(q):
    X=input()
    Y=input()
    A[i]=lcs(X,Y)

for i in range(q):
    print(A[i])

Python: """
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in xrange(len(s2) + 1)] for _ in xrange(2)]

	for i in xrange(1, len(s1) + 1):
		for j in xrange(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i & 1][j] = dp[1 - i & 1][j - 1] + 1
			else:
				dp[i & 1][j] = max(dp[1 - i & 1][j], dp[i & 1][j - 1])

	return dp[len(s1) & 1][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

Python: #JOI
def main():
    X=input()
    Y=input()
    dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
    for x in range(len(X)):
        for y in range(len(Y)):
            now=0
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            for x1 in range(Y[:y+1].count(X[x])):
                idx=now+Y[now:y+1].index(X[x])
                now=idx+1
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            now=0
            for y1 in range(X[:x+1].count(Y[y])):
                idx=now+X[now:x+1].index(Y[y])
                now=idx+1
                dp[x][y]=max(dp[idx-1][y-1]+1,dp[x][y])
    print(dp[len(X)-1][len(Y)-1])
for i in range(int(input())):
    main()