Go: // AOJ ALDS1_10_C: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

package main

import (
	"fmt"
)

func main() {
	var dataNum int
	var s1, s2 string

	fmt.Scanf("%d", &dataNum)

	for i := 0; i < dataNum; i++ {
		fmt.Scanf("%s", &s1)
		fmt.Scanf("%s", &s2)

		lcs := make([][]int, len(s1)+1)
		for j := 0; j < len(s1)+1; j++ {
			lcs[j] = make([]int, len(s2)+1)
		}

		for m, vs1 := range s1 {
			for n, vs2 := range s2 {
				if vs1 == vs2 {
					lcs[m+1][n+1] = lcs[m][n] + 1
				} else if lcs[m+1][n] > lcs[m][n+1] {
					lcs[m+1][n+1] = lcs[m+1][n]
				} else {
					lcs[m+1][n+1] = lcs[m][n+1]
				}
			}
		}

		// Answer
		fmt.Println(lcs[len(s1)][len(s2)])
	}
}

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
*/

C++: #if 0

#endif

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int Q;
int L[1000+10][1000+10];

int main() {
  cin >> Q;
  string X, Y;
  for (int i = 0; i < Q; i++) {
    for (int j = 0; j < 1000+10; j++) {
      L[0][j] = 0; L[j][0] = 0;
    }
    cin >> X >> Y;
    for (int x = 1; x <= X.length(); x++) {
      for (int y = 1; y <= Y.length(); y++) {
        if (X[x-1] == Y[y-1])
          L[x][y] = L[x-1][y-1] + 1;
        else
          L[x][y] = max(L[x-1][y], L[x][y-1]);
      }
    }
    cout << L[X.length()][Y.length()] << endl;
  }
}

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

int main(){
  int n;
  char x[1001],y[1001];
  int dp[1002][1002];
  


  //load n;
  cin >>n;
  for(int i=0;i<n;i++){
    //initialize
    for(int i=0;i<1002;i++){
      for(int j=0;j<1002;j++){
	dp[i][j]=0; 
      }
    }
    //load string
    scanf("%s",x);
    scanf("%s",y);
    //dp
    for(int j=0;j<strlen(x);j++){
      for(int k=0;k<strlen(y);k++){
	if(x[j]==y[k]){
	  dp[j+1][k+1]=dp[j][k]+1;
	}

	else{
 
	  if(dp[j][k+1]>dp[j+1][k]){
	    dp[j+1][k+1]=dp[j][k+1];
	  }

	  else{
	    dp[j+1][k+1]=dp[j+1][k];
	  }
	}
      }
    }

    //print
    cout <<dp[strlen(x)][strlen(y)]<<endl;
  }



  return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    {
        string t;
        getline(cin, t);
    }
    for(int i=0;i<n;i++) {
        string s1, s2;
        getline(cin, s1);
        getline(cin, s2);
        vector<int> v1(s2.size()+1, 0);
        vector<int> v2(s2.size()+1, 0);
        for(auto c1=s1.cbegin(); c1!=s1.cend(); ++c1) {
            int i = 1;
            for(auto c2=s2.cbegin(); c2!=s2.cend(); ++c2,i++) {
                auto m = max(v1[i], v2[i-1]);
                m = max(m, v1[i-1] + (*c1 == *c2 ? 1 : 0));
                v2[i] = m;
            }
            /*
            for(auto t=v1.begin();t!=v1.end();++t) {
                cout << *t << " ";
            }
            cout << endl;
            */
            swap(v1, v2);
        }
        cout << v1[s2.size()] << endl;
    }
}

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

#define MAX_NUM 1001
int fLength;
int sLength;

int memo[MAX_NUM][MAX_NUM];
string f, s;

/*******************
  Longest Common Subsequence
  ??¨??????????????§??????????????????(??¨??????????????§?????????)
 *********************/

void solve() {
  for(int i = 0; i < fLength; i++) {
    for(int j = 0; j < sLength; j++) {
      if(f[i] == s[j]) {
        memo[i + 1][j + 1] = memo[i][j] + 1;
      }
      else {
        memo[i + 1][j + 1] = max(memo[i + 1][j], memo[i][j + 1]);
      }
    }  
  }
}


int main(void) {
  int n;
  cin >> n;


  //?????????
  memset(memo, 0, sizeof(memo));
  for(int i = 0; i < n; i++) {
    cin >> f >> s;
    fLength = f.size();
    sLength = s.size();
    solve();
    cout << memo[fLength][sLength] << endl;
  }
  return 0;
}