Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const N = 1001

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func lcs(x, y string) int {
	var c [N][N]int
	m := len(x)
	n := len(y)
	var maxl int

	x = " " + x
	y = " " + y

	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-1][j], c[i][j-1])
			}
			maxl = max(maxl, c[i][j])
		}
	}
	return maxl
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())

	var out bytes.Buffer
	for i := 0; i < q; i++ {
		sc.Scan()
		s1 := sc.Text()
		sc.Scan()
		s2 := sc.Text()
		out.WriteString(fmt.Sprintf("%d\n", lcs(s1, s2)))
	}
	return strings.TrimRight(out.String(), "\n")
}

func main() {
	fmt.Println(answer(os.Stdin))
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

template<class T> inline void chmax(T& a, T b) { if (a < b) a = b; }
template<class T> inline void chmin(T& a, T b) { if (a > b) a = b; }


namespace Lcs
{

	int exec()
	{
		string S, T; cin >> S >> T;
		vector<vector<int>> dp(S.size() + 1, vector<int>(T.size() + 1, 0));
		for (int s = 0; s < S.size(); ++s) {
			for (int t = 0; t < T.size(); ++t) {
				if (S[s] == T[t]) dp[s + 1][t + 1] = dp[s][t] + 1;
				chmax(dp[s + 1][t + 1], dp[s + 1][t]);
				chmax(dp[s + 1][t + 1], dp[s][t + 1]);
			}
		}
		return dp[S.size()][T.size()];
	}
}

int main()
{
	int Q; cin >> Q;
	vector<int> anss(Q);
	for (int i = 0; i < Q; ++i) {
		anss[i] = Lcs::exec();
	}
	for (int i = 0; i < Q; ++i) {
		cout << anss[i] << endl;;
	}
}

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 <bits/stdc++.h>

using namespace std;
int main(int argc, const char * argv[]) {
    int q, i, m, n, sl1, sl2;
    cin >> q;
    vector<string> strlist;
    string str, str1, str2;
    for(i = 0;i < q;i++){
        cin >> str;
        strlist.push_back(str);
        cin >> str;
        strlist.push_back(str);
    }
    
    //start
    for(i = 0;i < q*2;i += 2){
        str1 = strlist[i];
        sl1 = str1.length();
        str2 = strlist[i+1];
        sl2 = str2.length();
        int dp[sl1+1][sl2+1];
        for(m = 0;m <= sl2;m++){
            dp[0][m] = 0;
        }
        for(m = 0;m <= sl1;m++){
            dp[m][0] = 0;
        }
        for(m = 1;m <= sl1;m++){
            for(n = 1;n <= sl2;n++){
                if(str1[m] == str2[n]){
                    dp[m][n] = dp[m-1][n-1] + 1;
                }else{
                    dp[m][n] = max(dp[m-1][n], dp[m][n-1]);
                }
            }
        }
        m = sl1;
        n = sl2;
        printf("%d\n", dp[m][n]);
        
    }
    return 0;
}

C++: #include <math.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <vector>

using namespace std;
using Graph = vector<vector<int>>;

using ll = long long;
typedef pair<ll, ll> P_ll;
typedef pair<int, int> P;

const ll INF_ll = 1e17;
const int INF = 1e8;

int main() {
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    string X, Y;
    cin >> X >> Y;
    vector<vector<int>> dp(X.size() + 1, vector<int>(Y.size() + 1, 0));
    for (int j = 0; j < X.size(); j++) {
      for (int k = 0; k < Y.size(); k++) {
        if (X[j] == Y[k]) {
          dp[j + 1][k + 1] = dp[j][k] + 1;
        } else {
          dp[j + 1][k + 1] = max(dp[j + 1][k], dp[j][k + 1]);
        }
      }
    }
    cout << dp[X.size()][Y.size()] << endl;
  }

  return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <utility>
#include <map>
#include <inttypes.h>

int LCS(std::string s,std::string t){
    int n,m,c[n+1][m+1];
    n=s.size();
    m=t.size();
    int maxlen=0;
    for(int i=0;i<=n;i++){
        c[i][0]=0; 
    }
    for(int i=0;i<=m;i++){
        c[0][i]=0;
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(s[i]==t[i]){
                c[i][j]=c[i-1][j-1]+1;
            }else{
                c[i][j]=std::max(c[i-1][j],c[i][j-1]);
            }
            maxlen=std::max(c[i][j],maxlen);
        }
    }
    return maxlen;
}
int main(){
	int N;
    
    std::cin >> N;
    std::string s1,s2;
    for(int i=0;i<N;i++){
        std::cin >> s1 >> s2;
        std::cout << LCS(s1,s2) <<std::endl;
    }
        
    
    return 0;
}

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

int lac(string x, string y) {
	int c[maxn][maxn];
	int m = x.size();
	int n = y.size();
	int maxl = 0;
	x = ' ' + x;
	y = ' ' + y;

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

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

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

int main() {
	int q;
	std::cin >> q;
	
	for (int i = 0; i < q; i++) {
		std::string s1, s2;
		std::cin >> s1 >> s2;
		std::vector<int> ref(s2.size(), 0);
		for (int j = 0; j < s1.size(); j++) {
			std::vector<int> vec = ref;
			for (int k = 0; k < s2.size(); k++) {
				if (s1[j] == s2[k]) {
					int al = k == 0 ? 0 : ref[k - 1];
					int a = ref[k];
					vec[k] = std::max(al + 1, a);
				}
				else {
					int l = k == 0 ? ref[0] : vec[k - 1];
					int a = ref[k];
					vec[k] = std::max(l, a);
				}
			}
			ref = vec;
		}
		std::cout << ref[s2.size() - 1] << std::endl;
	}
}

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

int main(){
  int n;
  char x[1001],y[1001];
  int dp[1010][1010];
  //load n;
  cin >>n;
  for(int i=0;i<n;i++){
    //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];
	  }


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



  return 0;
}

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

#define REP(i, n) for(int i = 0; i < (n); i++)

string str1, str2;
int dp[1001][1001];
int k;

int solve(int i, int j)
{
  if(dp[i][j] > 0)
    return dp[i][j];
  if(i == str1.size() || j == str2.size()){
    if(i != str1.size()){
      return solve(i + 1, k);
    }else{
      return 1;
    }
  }
  if(str1[i] == str2[j]){
    k = j + 1;
    dp[i][j] = solve(i + 1, j + 1);
    return dp[i][j] + 1;
  }else{
    return solve(i, j + 1);
  }
}

int main()
{
  int q, n, ans = 0;
  cin >> q;
  cin.ignore();
  fill(&dp[0][0], &dp[1001][0], -1);
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    if(str1.size() < str2.size())
      swap(str1, str2);
    REP(i, str1.size()){
      n = solve(i, 0) - 1;
      ans = (n > ans) ? n : ans;
    }
    cout << ans << endl;
    ans = 0;
  }
}