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

C++: #include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ull = uint64_t;

void print() { cout << endl; }
template <typename Head, typename... Tail>
void print(Head head, Tail... tail) {
    int size = sizeof...(Tail);
    cout << head;
    if (size > 0) {
        cout << " ";
    }
    print(tail...);
}

void print0() {}
template <typename Head, typename... Tail>
void print0(Head head, Tail... tail) {
    cout << head;
    print0(tail...);
}

struct xstruct {
    ll val;
};
bool operator<=(const xstruct& lhs, const xstruct& rhs) {
    return lhs.val <= rhs.val;
}
bool operator<(const xstruct& lhs, const xstruct& rhs) {
    return lhs.val < rhs.val;
}
bool operator>=(const xstruct& lhs, const xstruct& rhs) {
    return lhs.val >= rhs.val;
}
bool operator>(const xstruct& lhs, const xstruct& rhs) {
    return lhs.val > rhs.val;
}
bool operator==(const xstruct& lhs, const xstruct& rhs) {
    return lhs.val == rhs.val;
}
bool operator!=(const xstruct& lhs, const xstruct& rhs) {
    return lhs.val != rhs.val;
}
ostream& operator<<(ostream& os, xstruct const& xst) {
    return os << xst.val;
}

ll recursive(ll a, ll b, string& sa, string& sb, vector<vector<ll>>& dp) {
    ll maxval = 0;
    if (a == sa.length() || b == sb.length()) {
        return maxval;
    }
    if (dp[a][b] >= 0) {
        return dp[a][b];
    }

    if (sa.at(a) == sb.at(b)) {
        maxval = max(maxval, 1 + recursive(a + 1, b + 1, sa, sb, dp));
    }
    maxval = max(maxval, recursive(a + 1, b, sa, sb, dp));
    maxval = max(maxval, recursive(a, b + 1, sa, sb, dp));
    dp[a][b] = maxval;
    return dp[a][b];
}

int main() {
    ll N = 0;
    cin >> N;
    string nil;
    getline(cin, nil);
    for (ll iter = 0; iter < N; iter++) {
        string sa, sb;
        getline(cin, sa);
        getline(cin, sb);
        ll la = sa.length();
        ll lb = sb.length();

        vector<vector<ll>> dp(la, vector<ll>(lb));
        for (ll a = 0; a < la; a++) {
            for (ll b = 0; b < lb; b++) {
                dp[a][b] = -1;
            }
        }
        recursive(0, 0, sa, sb, dp);
        print(dp[0][0]);
    }
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <numeric>
#include <climits>
using namespace std;
//using ll = long long;
//const ll mod = 1000000007;
int n, m;
string s, t;
const int n_max = 1000;
const int m_max = 1000;

int main() {
	cin >> n;
	for(int k=0; k<n; ++k){
        cin >> s >> t;
        int dp[n_max+1][m_max+1] = {0};
	for (int i = 0; i < s.size(); ++i) {
		for (int j = 0; j < t.size(); ++j) {
			if (s[i] == t[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else {
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		}
	}
        cout << dp[s.size()][t.size()] << endl;
    }
	

	return 0;
}

C++: //#include "aizu.h"
#include <iostream>
#include <string>
#include <vector>

//namespace alds1_10_c{
template<class T>
T myMin(const T& arg){
	return arg;
}
template<class F, class... S>
F myMin(const F& first, const S&... second){
	F m = myMin(second...);
	if (m > first){
		return first;
	}else{
		return m;
	}
}
int f(std::string::iterator str1, const std::string& str2, const std::vector<int>& vec){
	std::vector<int> new_v;
	new_v.push_back(vec[0] + 1);
	{
		auto v = vec.begin() + 1;
		for (auto i = str2.begin(); i != str2.end(); ++i, ++v){
			if (*i == *str1){
				new_v.push_back(myMin(*v, *(v - 1), new_v.back()));
			}else{
				new_v.push_back(myMin(*v + 1, new_v.back() + 1));
			}
		}
	}
	if (*(++str1) != '\0'){
		return f(str1, str2, new_v);
	}else{
		return new_v.back();
	}
}
int main(){
	int n;
	std::cin >> n;
	for (int i = 0; i < n; ++i){
		std::string str1, str2;
		std::cin >> str1 >> str2;
		std::vector<int> vec;
    vec.push_back(0);
		for (int j = 0; j < str2.size(); ++j){
			vec.push_back(j);
		}
		std::cout << (str1.size() + str2.size() - f(str1.begin(), str2, vec)) / 2 << "\n";
	}
}
//}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
#define _A_ true
using namespace std;

int main(){
  int n,AC=0;
  int dp[1010][1010];
  char *A = new char[1500];
  char *B = new char[1500];

  scanf("%d",&n);
  while(_A_){
    if(AC == n)break;
    scanf("%s",A);
    scanf("%s",B);
    for(int i=0;i<1010;i++)for(int j=0;j<1010;j++)dp[i][j]=0;

    for(int i=0;i<strlen(A);i++){
      for(int j=0;j<strlen(B);j++){
	if(A[i] == B[j]){
	  dp[i+1][j+1]=dp[i][j]+1;
	}
	else{
	  if(dp[i+1][j] > dp[i][j+1]){
	    dp[i+1][j+1]=dp[i+1][j];
	  }
	  else {
	    dp[i+1][j+1] = dp[i][j+1];
	  }
	}
      }
    }
    printf("%d\n",dp[strlen(A)][strlen(B)]);
    AC++;
  }
  delete [] A;
  delete [] B;

  return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>

using namespace std;
static const int N=1000;
int lcs(string X, string Y){
    int m=X.size();
    int n=Y.size();
    int c[N+1][N+1];
    int maxl=0;
    X=' '+X;
    Y=' '+Y;
    int i,j;
    for(i=1;i<=m;i++)c[i][0]=0;
    for(j=1;j<=n;j++)c[0][j]=0;

    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][j-1],c[i-1][j]);
            }
            maxl=max(maxl,c[i][j]);
        }
    }
    return maxl;
}
int main()
{
    int n;
    string s1,s2;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s1>>s2;
        cout<<lcs(s1,s2)<<endl;
    }

    return 0;
}