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++: #define _GLIBCXX_DEBUG
typedef long long ll;
#include <bits/stdc++.h>

using namespace std;

ll mod = 1000000007;

template<class Type> inline bool chmax(Type& a, Type b) { if (a < b) { a = b; return 1; } return 0; }
template<class Type> inline bool chmin(Type& a, Type b) { if (a > b) { a = b; return 1; } return 0; }

template<class Type>
Type modpow(Type a, Type n, Type mod)
{
	Type res = 1;
	while (0 < n)
	{
		if (n & 1)
		{
			res = res * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

template<class Type>
Type gcd(Type x, Type y)
{
	Type r;
	if (x < y)
	{
		swap(x, y);
	}

	while (0 < y)
	{
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}

template<class Type>
bool isPrime(Type x)
{
	if (x == 2) return true;
	if (x < 2 || x % 2 == 0) return false;

	for (Type i = 3; i <= sqrt(x); i += 2)
	{
		if (x % i == 0) return false;
	}
	return true;
}

template<class Type>
vector<bool> eratos(Type n)
{
	vector<bool> isPrime(n + 1, true);
	isPrime[0] = isPrime[1] = false;
	for (Type i = 2; i <= n; i++)
	{
		if (isPrime[i])
		{
			Type j = i + i;
			while (j <= n)
			{
				isPrime[j] = false;
				j = j + i;
			}
		}
	}
	return isPrime;
}

bool binarySearchJudge(vector<int> a, int index, int key)
{
	if (key <= a[index]) return true;
	else return false;
}

int binarySearch(vector<int> a, int key)
{
	int ng = -1;
	int ok = a.size();
	while (1 < abs(ng - ok))
	{
		int mid = (ng + ok) / 2;
		if (binarySearchJudge(a, mid, key)) ok = mid;
		else ng = mid;
	}
	return a[ok] == key;
}

int lcs(string x, string y)
{
	int m = x.size();
	int n = y.size();
	vector<vector<int>> dp(m, vector<int>(n));

	dp[0][0] = (x[0] == y[0]) ? 1 : 0;
	for (int i = 1; i < m; i++)
	{
		if (y[0] == x[i]) dp[i][0] = 1;
		else dp[i][0] = max(dp[i - 1][0], 0);
	}
	for (int i = 1; i < n; i++)
	{
		if (x[0] == y[i]) dp[0][i] = 1;
		else dp[0][i] = max(dp[0][i - 1], 0);
	}

	for (int i = 1; i < m; i++)
	{
		for (int j = 1; j < n; j++)
		{
			if (x[i] == y[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	return dp[m - 1][n - 1];
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string x, y;
		cin >> x >> y;
		cout << lcs(x, y) << endl;
	}
}

C++: #include <iostream>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define MAX 100000

static const int N =100;

int lcs(string X,string Y){
  int c[N+1][N+1];
  int m=X.size();
  int n=Y.size();
  int ans=0;
  X= ' '+X;
  Y= ' '+Y;
  for(int i;i<=m;i++)c[i][0]=0;
  for(int j;j<=n;j++)c[0][j]=0;

  for(int i=1;i<=m;i++){
    for(int 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-1][j],c[i][j-1]);
      }
      ans=max(ans,c[i][j]);
    }
  
  }
  return ans;
}

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

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

#define MAX 1000

int lcs(string x, string y) {
  int c[MAX + 1][MAX + 1];
  int m = x.size();
  int n = y.size();
  int maxl = 0;
  x = ' ' + x;
  y = ' ' + y;
  for ( int i = 1; i <= m; i++ ) {
    for ( int 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 - 1][j], c[i][j - 1]);
      }
      maxl = max(maxl, c[i][j]);
    }
  }

  return maxl;
}

int main() {
  string s1, s2;
  int q;
  cin >> q;

  for ( int i = 0; i < q; i++ ) {
    cin >> s1 >> s2;
    cout << lcs(s1, s2) << endl;
  }

  return 0;
}

C++: #include<iostream>
#include<string>
using namespace std;
const int N_MAX = 1005;
short res[N_MAX][N_MAX];

int lcs(string X, string Y){
	int xLen = X.size();
	int yLen = Y.size();
	int maxRes=0;
	X=' '+X;
	Y=' '+Y;
	for(int i=1;i<=xLen;i++){
		for(int j=1;j<=yLen;j++){
			if(X[i]==Y[j]){
				res[i][j] = res[i-1][j-1]+1;
			}else if(res[i][j-1]>=res[i-1][j]){
				res[i][j] = res[i][j-1];
			}else{
				res[i][j] = res[i-1][j];
			}
			maxRes = (res[i][j]>maxRes)?res[i][j]:maxRes;
		}
	}
	return maxRes;
}

int main(){
	int n;
	string X, Y;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>X>>Y;
		cout<<lcs(X, Y)<<endl;
	}
}

C++: #include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define mp(a,b) make_pair((a),(b))
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int INF=1<<30;
const long long int INFLL=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

void solve_(){
     string a,b;
    cin >> a >> b;
    
    static int dp[1000][1000];
    fill_n((int*)dp,1000*1000,0);
    
    rep(i,0,a.size()){
        rep(j,0,b.size()){
            if(i!=0) dp[i][j]=dp[i-1][j];
            if(j!=0) dp[i][j]=max(dp[i][j],dp[i][j-1]);
            
            if(a[i]!=b[j]) continue;
            
            if(i==0&&j==0) dp[0][0]=1;
            else if(i==0) dp[0][j]=1;
            else if(j==0) dp[i][0]=1;
            else dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    
    cout << dp[a.size()-1][b.size()-1] << endl;
}

void solve(){
    int n;
    cin >> n;
    rep(i,0,n) solve_();
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	solve();
	return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX=1005;
int dp[MAX][MAX]={0};
int main(){
	string x,y;
	int q;
	cin>>q;
	while(q--){
		cin>>x>>y;
		memset(dp,0,sizeof(dp));
		x=" "+x;y=" "+y;
		for(int i=1;i<x.length();i++){
			for(int j=1;j<y.length();j++){
				if(x[i]==y[j])dp[i][j]=dp[i-1][j-1]+1;
				else {
					dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
				}
			}
		}
		cout<<dp[x.length()-1][y.length()-1]<<endl;
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstdlib>

int main(){
  int n;
  std::string x,y;
  std::cin>>n;
  int a[1000][1000];
  int b[n];

  for(int i=0;i<n;i++){
    std::cin>>x;
    std::cin>>y;
    for(int j=0;j<1000;j++){
      for(int k=0;k<1000;k++){
	a[j][k]=0;
      }
    }
    for(int j=0;j<x.size();j++){
      for(int k=0;k<y.size();k++){
	if(x[j]==y[k]){
	  a[j][k]=a[j-1][k-1]+1;
	}else{
	  if(a[j-1][k]>a[j][k-1]){
	    a[j][k]=a[j-1][k];
	  }else{
	    a[j][k]=a[j][k-1];
	  }
	}
      }
    }
    b[i]=a[x.size()-1][y.size()-1];
  }

  for(int i=0;i<n;i++){
  std::cout<<b[i]<<"\n";
  }

  return 0;
}