Go: package main

import "fmt"

func main() {
	var nPairs int
	fmt.Scanln(&nPairs)

	var a, b string
	for i := 0; i < nPairs; i++ {
		fmt.Scanln(&a)
		fmt.Scanln(&b)
		fmt.Println(lcsSize(a, b))
	}
}

func lcsSize(sa, sb string) int {
	dp := make([][]int, len(sa)+1)
	for i := 0; i <= len(sa); i++ {
		dp[i] = make([]int, len(sb)+1)
	}

	for a := 1; a <= len(sa); a++ {
		for b := 1; b <= len(sb); b++ {
			if sa[a-1] == sb[b-1] {
				dp[a][b] = dp[a-1][b-1] + 1
			} else {
				dp[a][b] = max(dp[a][b-1], dp[a-1][b])
			}
		}
	}

	return dp[len(sa)][len(sb)]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Python: def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))

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


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			elif dp1[j + 1] < dp1[j]:
				dp1[j + 1] = dp1[j]

	return dp1[-1]

if __name__ == '__main__':
	tc = int(raw_input())
	for _ in range(tc):
		print(lcs())

Python: import sys


def lcs(X, Y):
    len_x = len(X)
    dp = [0] * (len_x + 1)

    for y in Y:
        _dp = dp[:]
        for j, x in enumerate(X):
            if x == y:
                dp[j + 1] = _dp[j] + 1
    
            elif _dp[j + 1] < dp[j]:
                dp[j + 1] = dp[j]

    return dp[len_x]


n = int(sys.stdin.readline())
for i in range(n):
    X = sys.stdin.readline().rstrip()
    Y = sys.stdin.readline().rstrip()
    print(lcs(X, Y))

Python: def lcs(m,n):
    N = len(n)
    dp = [0]*(N+1)
    for x in m:
        cp_dp = dp[:]
        for i ,y in enumerate(n):
            if x == y :
                dp[i+1] = cp_dp[i] +1 
            else:
                if dp[i+1] < dp[i]:
                    dp[i+1] = dp[i]
    return dp[N]

a = int(input())

for b in range(a):
    m = input()
    n = input()
    print(lcs(m,n))

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: """
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 range(len(s2) + 1)] for _ in range(len(s1) + 1)]

	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][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

	return dp[len(s1)][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: n = int(input())

for k in range(n):
    a = input()
    b = input()
    len_a, len_b = len(a), len(b)
    table = [[0] * (len_b +1) for i in range(len_a + 1)]
    
    for i in range(len_a):
        a_i = a[i]
        for j in range(len_b):
            if a_i == b[j]:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = max(table[i][j+1],table[i+1][j])
    print(table[len_a][len_b])

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+1)][len(s2+1)])
for a in ans:
    print(a)

Python: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  s=0
  for i,k in enumerate(z):
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))

Python: from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(m + 2) for a in range(n + 2)]
    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 max(max(c))

n = int(input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    # s1 = strs[i*2].rstrip()
    # s2 = strs[i*2+1].rstrip()
    ret.append(lcs(strs[i*2].rstrip(), strs[i*2+1].rstrip()))
print(*ret, sep="\n")

Python: def lcs(X, Y):
    row, colums = len(X) + 1, len(Y) + 1
    lcs_list = [[0 for y in range(colums)] for x in range(row)]
    for i in range(row):
        for j in range(colums):
            if i == 0 or j == 0:
                lcs_list[i][j] = 0
            elif X[i-1] == Y[j-1]:
                lcs_list[i][j] = lcs_list[i-1][j-1] + 1
            else:
                lcs_list[i][j] = max(lcs_list[i][j-1], lcs_list[i-1][j])
    return lcs_list[-1][-1]

import sys
n = int(input())
input_lines = sys.stdin.readlines()
for i in range(n):
    X = list(input_lines[2*i].rstrip())
    Y = list(input_lines[2*i+1].rstrip())
    print(lcs(X,Y))

Python: import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))


run()

Python: m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for j in range(len(str1)):
        for k in range(len(str2)):
            if(str1[j]==str2[k]):
                A[k+1] = A[k+1]+1
            else:
                if(A[k] > A[k+1]):
                    A[k+1] = A[k]
    print(A[-1])

Python: def length_of_lcs(x, y):
    n = len(y)
    #pre_row = [0] * (n + 1)
    cur_row = [0] * (n + 1)
    for x_c in x:
        prev_row = cur_row[:]
        for j, y_c in enumerate(y):
            if x_c == y_c:
                cur_row[j+1] = prev_row[j] + 1
            elif cur_row[j] > cur_row[j+1]:
                cur_row[j+1] = cur_row[j]

    return cur_row[n]


if __name__ == '__main__':
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(length_of_lcs(x, y))

Python: def lcs(X, Y):
    dp = []
    for y in Y:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = X.find(y, bgn_idx) + 1
            
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = X.find(y, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

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