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 <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(){
	int q;
	cin >> q;
	vector<int> ans(q);
	for(int i = 0;i < q;i++){
		string s,t;
		cin >> s >> t;
		int n = s.size();
		int m = t.size();

		vector<vector<int>> dp(n+1,vector<int>(m+1,0));

		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(s[i] == t[j]){
					dp[i+1][j+1] = max({dp[i][j+1],dp[i+1][j],dp[i][j]+1});
				}
				else{
					dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);    
				}
			}
		}
		ans[i] = dp[n][m];
	}

	for(int a:ans)cout << a << endl;
}

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

using namespace std;

int solve(string s1, string s2){
    int L[s1.size()+1][s2.size()+1];
    for(int i=0;i<=s1.size();i++){
        for(int j=0;j<=s2.size();j++){
            if(i==0 || j==0){
                L[i][j]=0;
            }
            else if(s1[i] == s2[j]){
                L[i][j] = 1 + L[i-1][j-1];
            }
            else{
                L[i][j] = max(L[i][j-1],L[i-1][j]);
            }
        }
    }
    return L[s1.size()][s2.size()];
}

int main(){
    int n ; cin >> n;
    for(int i=0;i<n;i++){
        string s1,s2; cin>> s1 >> s2;
        cout << solve(s1,s2) << endl;
    }
}

C++: #include<algorithm>
#include<string>
#include<vector>
#include<iostream>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

ll gcd(ll a,ll b)
{
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

ll lcm(ll a,ll b)
{
   return a/gcd(a,b)*b;
}

//累乗だってさ
ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}
//逆元だってさ
ll modinv(ll a,ll mod1) {
    return modpow(a, mod1 - 2, mod1);
}

const ll MAX = 1000000;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin>>n;
    vector<ll> ans(n);
    rep(i,n){
        string x,y;
        cin>>x>>y;
    
        ll dp[1010][1010]={0};
        rep(i,y.size()) dp[0][i]=0;
        
        rep(i,x.size()){
            for(ll j=0;j<y.size();j++){
                if(x.at(i)==y.at(j)) dp[i+1][j+1]=max(dp[i+1][j+1],1+dp[i][j]);
                else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
            }
        }
        ans[i]=dp[x.size()][y.size()];
    }
    rep(i,n) cout<<ans[i]<<endl;
    return 0;
}

C++: #include <iostream>
#include <string>
#define int long long
//#define _DEBUG
using namespace std;
string sa, sb;
int T[1000][1000];
int solve(){
    int sal = sa.length(), sbl = sb.length();
    for(int a=0; a<=sal; a++){
        for(int b=0; b<=sbl; b++){
            if(a==0 || b==0){
                T[a][b] = 0;
            }else if(sa[a-1] == sb[b-1]){
                T[a][b] = 1 + T[a-1][b-1];
            }else{
                T[a][b] = max(T[a][b-1], T[a-1][b]);
            }
        }
    }
    return T[sal][sbl];
}
signed main(){
    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> sa >> sb;
        cout << solve() << endl;
    }
}

C++: #include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct LongestCommonSubstring{
  struct node{
    int value;
    node *next;
    node(int value,node *next):value(value),next(next){}
  };
  const int INF=1<<28;
  string x,y;
  LongestCommonSubstring(){}
  LongestCommonSubstring(string x,string y):x(x),y(y){}
  string lcs(){
    int n=x.size(),m=y.size();
    map<char,vector<int> > M;
    for(int j=m-1;j>=0;j--) M[y[j]].push_back(j);
    vector<int> xs(n+1,INF);
    xs[0]=-INF;
    vector<node* > link(n+1);
    for(int i=0;i<n;i++){
      if(M.count(x[i])){
	vector<int> ys=M[x[i]];
	for(int j=0;j<(int)ys.size();j++){
	  int k=distance(xs.begin(),lower_bound(xs.begin(),xs.end(),ys[j]));
	  xs[k]=ys[j];
	  link[k]=new node(y[ys[j]],link[k-1]);
	}
      }
    }
    string res;
    int l=distance(xs.begin(),lower_bound(xs.begin(),xs.end(),INF-1))-1;
    for(node *p=link[l];p!=NULL;p=p->next)
      res.push_back(p->value);
    return res;
  }
};
//END CUT HERE
signed main(){
  int q;
  cin>>q;
  while(q--){
    string x,y;
    cin>>x>>y;
    LongestCommonSubstring lcs(x,y);
    cout<<lcs.lcs().size()<<endl;
  }
  return 0;
}
/*
verified on 2017/06/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=jp
*/