Go: package main

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

var (
	nstr   func() string
	stdout *bufio.Writer
)

func init() {
	nstr = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func main() {
	defer stdout.Flush()

	n := nint()
	xList := make([]string, n)
	yList := make([]string, n)

	for i:=0;i<n ;i++  {
		xList[i] = nstr()
		yList[i] = nstr()
	}

	for i := 0; i<n	; i++  {
		fmt.Println(lcs(xList[i], yList[i]))
	}

}

func lcs(x string, y string) int{
	var m = len(x)
	var n = len(y)

	c := make([][]int, m+1)
	for i:= range c{
		c[i] = make([]int, n+1)
	}
	for i:=	1;i<=m ;i++  {
		for j:=1;j<=n ;j++  {
			if x[i-1] == y[j-1]{
				c[i][j] = c[i-1][j-1] + 1
			}else{
				c[i][j] = int(math.Max(float64(c[i-1][j]), float64(c[i][j-1])))
			}


		}
	}
	return c[m][n]

}


func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func nint64() int64 {
	i, err := strconv.ParseInt(nstr(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func nint() int {
	return int(nint64())
}

func getIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = nint()
	}
	return b
}

func getStringSlice(n int) []string {
	b := make([]string, n)
	for i := 0; i < n; i++ {
		b[i] = nstr()
	}
	return b
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

func contains(s []int, e int) bool {
	for _, a := range s {
		if a == e {
			return true
		}
	}
	return false
}

func bin(i int, prefix bool) string {
	i64 := int64(i)

	if prefix {
		return "0b" + strconv.FormatInt(i64, 2)
	} else {
		return strconv.FormatInt(i64, 2)
	}
}

func strReverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}

	return string(runes)
}

Python: # -*- coding: utf-8 -*-
"""
Created on Fri May  4 20:33:37 2018
ALDS1_10_C Using Numpy
@author: maezawa
"""

import numpy as np

def longest(x, y):
    m = len(x)
    n = len(y)
    maxl = 0
    c = np.zeros((m+1, n+1), dtype=int)
    for i in range(m):
        for j in range(n):
            #print(i,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

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

Python: n = int(input())
dataset = []
for i in range(n):
    tmp = []
    tmp.append(input())
    tmp.append(input())
    dataset.append(tmp)
 
for data in dataset:
    m = len(data[0])
    n = len(data[1])
    dp = []
    for x in range(n+1):
        dp.append([0] *(m+1))
 
    for j in range(n):
        for i in range(m):
            if data[0][i] == data[1][j]:
                dp[j+1][i+1] = dp[j][i] + 1
            else:
                #dp[j+1][i+1] = max(dp[j+1][i], dp[j][i+1])
                dp[j+1][i+1] = dp[j+1][i] if dp[j+1][i]>dp[j][i+1] else dp[j][i+1]
    print(dp[n][m])

Python: def lcs_len(x, y):
    ly = len(y)
    tcsl = [0] * (ly + 1)
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            elif tcsl[j] < tcsl[j - 1]:
                tcsl[j] = tcsl[j - 1]
    print(tcsl[j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)

Python: import sys

def dp_init(m, n):
    return [[0] * n] * m

def solve(str_a, str_b):
    dp = dp_init(len(str_a), len(str_b))
    return rec(0, 0, str_a, str_b)

def rec(i, j, str_a, str_b):
    if i == 0 or j == 0:
        return 0
    if dp[i][j] > 0:
        return dp[i][j]
    if str_a[i-1] == str_b[j-1]:
        dp[i][j] = rec(i-1, j-1, str_a, str_b) + 1
        return dp[i][j]
    dp[i][j] = max(rec(i, j-1, str_a, str_b), rec(i-1, j, str_a, str_b))
    return dp[i][j]

nb_pairs = int(input())
pairs = []
for i in range(0, nb_pairs):
    pairs.append((input(), input()))

for i in range(0, nb_pairs):
    str_a, str_b = pairs[i]
    print(solve(str_a, str_b))

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: #dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")

Python: def solveZ(X, Y, Z, x, y):
  if x < len(X) and y < len(Y):
    ans = [solveZ(X, Y, Z, x, y+1)]
    for j in range(x, len(X)):
      if Y[y] == X[j]:
        Z2 = Z + str(Y[y])
        ans.append(solveZ(X, Y, Z2, j+1, y+1))
        break
    return max(ans)
  else:
    print(Z)
    return len(Z)

q = int(input())
ans = [[] for i in range(q)]
for i in range(q):
  X = str(input())
  Y = str(input())
  ans[i] = solveZ(X, Y, "", 0, 0)

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

Python: for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        pre = dp[x-1]
        tmp = dp[x]
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                tmp[y] = pre[y-1] + 1
            else:
                tmp[y] = max(tmp[y-1], pre[y])
    print(dp[-1][-1])

Python: def findlcs(x, y):
    dp = [0]*(len(y)+1)

    for c in x:
        tmp = dp[:]
        for j in range(len(y)):
            if c == y[j]:
                dp[j+1] = tmp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]

    return dp[-1]


q = int(input())
for k in range(q):
    X = input()
    Y = input()
    print(findlcs(X, Y))

Python: def LCS(X, Y):
    n = len(X)
    m = len(Y)
    T = [0]*(n+1)
    
    for j in range(m):
        T_old = T[:]
        c = Y[j]
        for i in range(n):
            if X[i] == c:
                T[i] = T_old[i-1] + 1
            elif T[i-1] > T[i]:
                T[i] = T[i-1]            
    return T[len(X)-1] 



q = int(input())
for cnt in range(q):
    X = input()
    Y = input()
    print(LCS(X, Y))

Python: def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    x = " " + x
    y = " " + y
    maxl = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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

if __name__ == '__main__':
    n = int(input().rstrip())
    for i in range(n):
        s1 = input().rstrip()
        s2 = input().rstrip()
        print(lcs(s1, s2))