Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	Q := sc.nextInt()
	for q := 0; q < Q; q++ {
		X, Y := sc.nextStr(), sc.nextStr()
		xLen, yLen := len(X), len(Y)
		dp := make([][]int, xLen+1)
		for i := 0; i <= xLen; i++ {
			dp[i] = make([]int, yLen+1)
		}
		for x := 0; x <= xLen; x++ {
			for y := 0; y <= yLen; y++ {
				if x == 0 || y == 0 {
					dp[x][y] = 0
				} else if X[x-1] == Y[y-1] {
					dp[x][y] = dp[x-1][y-1] + 1
				} else {
					dp[x][y] = max(dp[x-1][y], dp[x][y-1])
				}
			}
		}
		fmt.Fprintln(wtr, dp[xLen][yLen])
	}

	wtr.Flush()
}

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()