Go: package main

import (
	. "fmt"
    "math"
)

// func init() { Println("----------------------------------------") }

func main() {
    const L_MAX = 1003

	var q int
	Scanf("%d", &q)
	X := make([]string, 0, 150)
	Y := make([]string, 0, 150)
	for i := 0; i < 2 * q; i++ {
	    var tmp string
	    Scanf("%s", &tmp)

	    if i % 2 == 0 {
	        X = append(X, tmp)
	    } else {
	        Y = append(Y, tmp)
	    }
	}

    for i := 0; i < q; i++ {
        dp := make([][]int, L_MAX)
        for k, _ := range dp {
            dp[k] = make([]int, L_MAX)
        }

        x, y := X[i], Y[i]

        // init
        isXFound := false
        for c := 0; c < len(x); c++ {
            if isXFound || y[0] == x[c] {
                dp[0][c] = 1
                isXFound = true
            }
        }
        isYFound := false
        for r := 0; r < len(y); r++ {
            if isYFound || x[0] == y[r] {
                dp[r][0] = 1
                isYFound = true
            }
        }

        for r := 1; r < len(y); r++ {
            for c := 1; c < len(x); c++ {
                // dp[r][c]
                if x[c] == y[r] {
                    dp[r][c] = int(math.Max(float64(dp[r - 1][c - 1] + 1), float64(dp[r][c])))
                }

                dp[r][c] = int(math.Max(float64(dp[r][c]), math.Max(float64(dp[r - 1][c]), float64(dp[r][c - 1]))))
            }
        }
        Println(dp[len(y) - 1][len(x) - 1])

        // LCSも求めておく
        // ans := ""
        // r, c := len(y) - 1, len(x) - 1
        // for r >= 0 && c >= 0 {
        //     if y[r] == x[c] {
        //         ans = string(x[c]) + ans
        //         r--
        //         c--
        //     } else {
        //         if dp[r - 1][c] > dp[r][c - 1] {
        //             r--
        //         } else {
        //             c--
        //         }
        //     }
        // }
        // Println(ans)
    }
}

C++: // clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever while (true)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
using namespace std;
// clang-format on

template<typename T> int LCS(const T &a, const T &b) {
  const int n = a.size(), m = b.size();
  vvi dp(n + 1, vi(m + 1));
  rep(i, n) rep(j, n) {
    if (a[i] == b[j]) cmax(dp[i + 1][j + 1], dp[i][j] + 1);
    cmax(dp[i + 1][j + 1], max(dp[i + 1][j], dp[i][j + 1]));
  }
  return dp.back().back();
}

main {
  int n;
  cin >> n;
  while (n--) {
    string x, y;
    cin >> x >> y;
    cout << LCS(x, y) << endl;
  }
}

C++: #include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long 
//写し
int q, dp[1007][1007]; string s, t;
int main() {
	cin >> q;
	rep(i,q){
		cin >> s >> t;
		for(int i = 0; i < s.size(); i++) {
			for(int j = 0; j < t.size(); j++) {
        if(s[i] == t[j]){
          dp[i + 1][j + 1] = dp[i][j] + 1;
        }else{
          dp[i + 1][j + 1] =  max(dp[i][j + 1], dp[i + 1][j]); 
        }
			}
		}
		cout << dp[s.size()][t.size()] << endl;
	}
  return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
using namespace std;
static const int N =1000;
int lcs(string X,string Y){
  int c[N+1][N+1];
  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(){
  string s1,s2;
  int n; cin >> n;
  for(int i=0;i<n;i++){
    cin >> s1 >> s2;
    cout << lcs(s1,s2) << endl;
  }
  return 0;
}

C++: #include<iostream>
#include<string>
int main()
{
  int n;
  int an[1000];
  int l=0;
  std::cin>>n;
  std::string x;
  std::string y;
  int ans[10000][10000];
  int j,k;
  for(int i=0;i<n;i++){
    std::cin>>x;
    std::cin>>y;
    for(int j=0;j<10000;j++){
      for(int k=0;k<10000;k++){
	ans[j][k]=0;
      }
    }
    for(int j=0;j<x.size();j++){
      for(int k=0;k<y.size();k++){
	if(x[j]==y[k]){
	  ans[j][k]=ans[j-1][k-1]+1;
	}else{
	  if(ans[j][k-1]>ans[j-1][k]){
	    ans[j][k]=ans[j][k-1];
	  }else{
	    ans[j][k]=ans[j-1][k];
	  }
	}
      }
    }
    std::cout<<ans[x.size()-1][y.size()-1]<<'\n';  
  }
  return 0;
}

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

int dp[1001][1001];

int lcs(std::string X, std::string Y){
	int m,n,i,j;
	m = X.length();
	n = Y.length();
	for(i=0;i<std::max(m,n)+1;i++){
			dp[i][0] = 0;
			dp[0][j] = 0;
	}
	
	for (i=0;i<m;i++){
		for(j=0;j<n;j++){
			if(X[i] == Y[j]){
				dp[i+1][j+1] = dp[i][j] +1;
			}
			else{
				dp[i+1][j+1] = std::max(dp[i][j+1], dp[i+1][j]);
			}
		}
	}
	return dp[m][n];
}
int main(void){
	int i,q,n,m;
	std::string str1, str2;
	std::cin >> q;
	for (i=0;i<q;i++){
		std::cin >> str1;
		std::cin >> str2;
		std::cout << lcs(str1, str2) << std::endl;
	}
	return 0;
}

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

static const int N = 1000;


int lcs(string X, string Y) {
	int c[N + 1][N + 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[i]) {
				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 n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s1 >> s2;
		cout << lcs(s1, s2) << endl;
	}
	return 0;
}

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

int lcs(string X, string Y) {
  int dp[1000 + 1][1000 + 1];
  int max = 0;
  int m = X.size();
  int n = Y.size();
  X = ' ' + X;
  Y = ' ' + Y;

  for (int i = 1; i <= m; i++)
    dp[i][0] = 0;

  for (int i = 1; i <= n; i++)
    dp[0][i] = 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 if (dp[i - 1][j] >= dp[i][j - 1])
	dp[i][j] = dp[i - 1][j];
      else
	dp[i][j] = dp[i][j - 1];

      max = (max < dp[i][j]) ? dp[i][j] : max;
    }
  }

  return max;
}

int main(int argc, char const *argv[]) {
  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    string X, Y;
    cin >> X >> Y;

    cout << lcs(X, Y) << endl;
  }

  return 0;
}