Go: package main

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

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func f() {
	var S, T string
	fmt.Scan(&S)
	fmt.Scan(&T)
	lenS, lenT := len(S), len(T)
	dp := make([][]int, lenS+1)
	for i:=0; i<lenS+1; i++ {
		dp[i] = make([]int, lenT+1)
	}
	for i:=1; i<lenS+1; i++ {
		for j:=1; j<lenT+1; j++ {
			if S[i-1] == T[j-1] {
				dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	fmt.Println(dp[lenS][lenT])
}

func main(){
	var n int 
	fmt.Scan(&n)
	for i:=0; i<n; i++ {
		f()
	}
}

C++: #include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    int N;
    cin >> N;
    for(int c=0; c<N; ++c){
        string X,Y;
        cin >> X >> Y;
        int xlen = (int)X.size();
        int ylen = (int)Y.size();

        vector<vector<int> > L(xlen+1 ,vector<int>(ylen+1, 0));

        for(int i=1;i<=xlen;++i){
            for(int j=1;j<=ylen;++j){
                if(X[i-1] == Y[j-1]){
                    L[i][j] = L[i-1][j-1] + 1;
                } else {
                    L[i][j] = max(L[i-1][j], L[i][j-1]);
                }
            }
        }
        cout << L[xlen][ylen] << endl;
    }
}

C++: // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

#define debug(x) cout << #x << "==" << x << endl;

using namespace std;

//??\???
#define MAX_LEN 1000
int N;
int dp[MAX_LEN + 1][MAX_LEN + 1];

void print_dp_table(int n, int m) {
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cout <<setw(2) << dp[i][j];
    }
    cout << "\n";
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false);

  cin >> N;

  string s1, s2;

  while( cin >> s1 >> s2 ) {

    std::vector<char> a;
    std::vector<char> b;
    for(char& c : s1) {
      a.push_back(c);
    }
    for(char& c : s2) {
      b.push_back(c);
    }


    // dp ????????????????????????
    fill(dp[0], dp[MAX_LEN + 1], 0);

    for( int i = 0; i < (int)a.size(); i++) {
      for( int j = 0; j < (int)b.size(); j++) {
        if( a[i] == b[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]);
        }
      }
    }

    // print_dp_table(a.size(), b.size());
    cout << dp[a.size()][b.size()] << endl;

  }

  return 0;
}

C++: #include<iostream>
#include<cstring>
using namespace std;
int main(){
  int n; cin>>n;
  for(int i=0;i<n;++i){
    char str1[1001],str2[1001]; cin>>str1>>str2;
    int len1=strlen(str1),len2=strlen(str2);
    int dp[1001][1001]={},max=0;
    for(int i=0;i<len1;++i){
      for(int j=0;j<len2;++j){
	if(str1[i]==str2[j]) dp[i+1][j+1]=dp[i][j]+1;
	else{
	  if(dp[i][j+1]<dp[i+1][j]) dp[i+1][j+1]=dp[i+1][j];
	  else dp[i+1][j+1]=dp[i][j+1];
	}
	if(max<dp[i+1][j+1]) max=dp[i+1][j+1];
      }
    }
    cout<<max<<endl;
  }
  return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
//#define INF 1<<31-1
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
//typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
int INF=INT_MAX;

using namespace std;

int main(){
    string s,t;
    int n;
    cin>>n;
    rep(i,0,n){
        cin>>s>>t;
        vector<vector<int>> v(s.size()+1,vector<int>(t.size()+1));
        int ans=0;
        
        rep(i,0,s.size())v[i][0]=0;
        rep(i,0,t.size())v[0][i]=0;
        
        rep(i,1,s.size()+1){
            rep(j,1,t.size()+1){
                if(s[i]==t[j]){
                    v[i][j]=v[i-1][j-1]+1;
                }else {
                    v[i][j]=max(v[i-1][j],v[i][j-1]);
                }
            ans=max(ans,v[i][j]);
            }
        }
        cout<<ans<<endl;
    }
    
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
template<class T>
void puta(T&&t){cout<<t<<endl;}
template<class H,class...T>
void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}

int popcnt(int x){return __builtin_popcount(x);}
int popcnt(ll x){return __builtin_popcountll(x);}
int bsr(int x){return 31 - __builtin_clz(x);}
int bsr(ll x){return 63 - __builtin_clzll(x);}
int bsf(int x){return __builtin_ctz(x);}
int bsf(ll x){return __builtin_ctzll(x);}
template<class T>T chmax(T&a,T b){return a=a>b?a:b;}
template<class T>T chmin(T&a,T b){return a=a<b?a:b;}
/*他のライブラリを入れる場所*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int d;
	cin>>d;
	rep(_,d){
		string s,t;
		cin>>s>>t;
		int n=s.size(),m=t.size();
		vvi dp(n+1,vi(m+1,0));
		rep(i,n){
			dp[i+1]=dp[i];
			rep(j,m){
				if(s[i]==t[j]){
					chmax(dp[i+1][j+1],dp[i][j]+1);
				}else{
					chmax(dp[i+1][j+1],dp[i+1][j]);
				}
			}
	//		cout<<dp[i]<<endl;
		}
	//	cout<<dp[n]<<endl;
		cout<<dp[n][m]<<endl;
	}
	return 0;
}