Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const N = 1001

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func lcs(x, y string) int {
	var c [N][N]int
	m := len(x)
	n := len(y)
	var maxl int

	x = " " + x
	y = " " + y

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if x[i] == y[j] {
				c[i][j] = c[i-1][j-1] + 1
			} else {
				c[i][j] = max(c[i-1][j], c[i][j-1])
			}
			maxl = max(maxl, c[i][j])
		}
	}
	return maxl
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())

	var out bytes.Buffer
	for i := 0; i < q; i++ {
		sc.Scan()
		s1 := sc.Text()
		sc.Scan()
		s2 := sc.Text()
		out.WriteString(fmt.Sprintf("%d\n", lcs(s1, s2)))
	}
	return strings.TrimRight(out.String(), "\n")
}

func main() {
	fmt.Println(answer(os.Stdin))
}

Python: q=int(input())
for i in range(q):
    s1=input()
    s2=input()
    ls1=len(s1)
    ls2=len(s2)
    f=[[0 for k in range(ls2+1)] for j in range(ls1+1)]
    for j in range(1,ls1+1):
        tmp=s1[j-1]
        for k in range(1,ls2+1):
            if tmp==s2[k-1]:
                f[j][k]=f[j-1][k-1]+1
            else:
                f[j][k]=max(f[j-1][k],f[j][k-1])
    print(f[j][k])

Python: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  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: q = int(input())

for i in range(q):
    X = input()
    Y = input()
    x = len(X)
    y = len(Y)
    dp = [[0] * (y + 1)] * (x + 1)
    ans = 0
    for j in range(1, x+1):
        for k in range(1, y+1):
            X_j = X[:j]
            Y_k = Y[:k]
            if X_j[-1] == Y_k[-1]:
                dp[j][k] = dp[j - 1][k - 1] + 1
            else:
                dp[j][k] = max(dp[j - 1][k],dp[j][k - 1])
            ans = max(ans, dp[j][k])
    print(ans)

Python: n=int(input())

l=[]

for i in range(n):
	a=list(input())
	b=list(input())
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	if a[0]==b[0]:
		dp[0][0]=1
	for i in range(1,len(a)):
		if a[i]==b[0]:
			dp[i][0]=1
		else:
			dp[i][0]=dp[i-1][0]
	for i in range(1,len(b)):
		if a[0]==b[i]:
			dp[0][i]=1
		else:
			dp[0][i]=dp[0][i-1]
	for i in range(1, len(a)):
		for j in range(1, len(b)):
			if a[i]==b[j]:
				dp[i][j]=dp[i-1][j-1]+1
			else:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])

	l.append(dp[len(a)-1][len(b)-1])

for i in l:
	print(i)

Python: a=[]
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]
 a+=[len(z)]
print(*a,sep='\n')

Python: def longest_common_seq(x, y):
    m, n = len(x), len(y)
    
    dp = []
    for _ in range(m+1):
        dp.append([0]*(n+1))

    for i in range(m):
        for j in range(n):
            if x[i] == y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m-1][n-1]



if __name__ == '__main__':
    q = int(input())  # 1 .. 150
    for _ in range(q):
        x = input()
        y = input()
        print(x, y)
        l = longest_common_seq(x,y)
        print(l)

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


def lcs(X, Y):
    memo = dict()
    for i in range(len(X)+1):
        memo[(i, 0)] = 0
    for j in range(len(Y)+1):
        memo[(0, j)] = 0
    for i, x in enumerate(X):
        plus_flag = False
        for j, y in enumerate(Y):
            if x == y and (not plus_flag):
                memo[(i+1,j+1)] = max(memo[i, j+1], memo[i+1, j]) + 1
                plus_flag = True
            else:
                memo[(i+1,j+1)] = max(memo[i, j+1], memo[i+1, j])
    return memo[(len(X), len(Y))]


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

Python: def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        c2 = c1[:]
        for j in range(n):
            if (d == Y[j]):
                c1[j + 1] = c2[j] + 1
            elif (c1[j + 1] < c1[j]):
                c1[j + 1] = c1[j]
    return (c1[-1])
 
q = int(input().rstrip())
t = []
for i in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep = "\n")

Python: from bisect import bisect_left
q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    p = []
    for i, c in enumerate(s1):
        s = 0
        while True:
            j = s2[s:].find(c)
            if j == -1:
                break
            p.append((i, s+j))
            s += j+1

    lis = []
    for _, y in sorted(p):
        i = bisect_left(lis, y)
        if len(lis) <= i:
            lis.append(y)
        else:
            lis[i] = y
    print(len(lis))

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 lcs(x, y):
    lx = len(x)
    ly = len(y)
    pcsl = [[0 for j in range(ly + 1)] for i in range(lx + 1)]
    for i in range(lx):
        for j in range(ly):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            else:
                pcsl[i][j] = max(pcsl[i - 1][j], pcsl[i][j - 1])
    print(pcsl[i][j])


import sys

q = sys.stdin.readline()

while True:
    ax = sys.stdin.readline()[:-1]
    ay = sys.stdin.readline()[:-1]
    lcs(ax, ay)

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: q = int(input())

for i in range(q):
    x = list(input())
    y = list(input())
    max_count = 0
    for j in range(len(x)):
        for k in range(len(y)):
            count = 0
            if x[j] == y[k]:
                count += 1 
                ret = j
                ret_2 = k
                while j < len(x) -1 and k < len(y) -1:
                    j += 1
                    k += 1
                    if x[j] == y[k]:
                        count += 1
                    else:
                        break
                j = ret
                k = ret_2
                max_count = max(count,max_count)
    print(max_count)

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):
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in xrange(1, la + 1):
		dp2 = dp1[0:]
		for j in xrange(1, lb + 1):
			if s1[i - 1] == s2[j - 1]:
				dp1[j] = dp2[j - 1] + 1
			else:
				dp1[j] = max(dp1[j - 1], dp2[j])

	return dp1[-1]

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

Python: import sys
e=sys.stdin.readline
for _ in[0]*int(e()):
 X,z=e(),[]
 for y in e():
  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)-1)