Go: package main

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

type Position struct {
	X int
	Y int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}
	for i := 0; i < n; i++ {
		strX := nextText(sc)
		strY := nextText(sc)
		fmt.Println(calcLcs(strX, strY))
	}
}

func calcLcs(strX, strY string) int {
	return lcs(strX, strY, Position{0, 0}, make(map[Position]int))
}

func lcs(strX string, strY string, position Position, memo map[Position]int) int {
	if position.X >= len(strX) || position.Y >= len(strY) {
		return 0
	}
	if v, ok := memo[position]; ok {
		return v
	}
	if strX[position.X] == strY[position.Y] {
		result := lcs(strX, strY, Position{position.X + 1, position.Y + 1}, memo)
		memo[position] = result + 1
		return memo[position]
	} else {
		result1 := lcs(strX, strY, Position{position.X + 1, position.Y}, memo)
		result2 := lcs(strX, strY, Position{position.X, position.Y + 1}, memo)
		var result int
		if result1 > result2 {
			result = result1
		} else {
			result = result2
		}
		memo[position] = result
		return result
	}
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

C++: #include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int q;
    cin >> q;
    rep (_, q)
    {
        string x, y;
        cin >> x >> y;
        int nx = x.size();
        int ny = y.size();

        int dp[nx + 1][ny + 1];
        rep (i, nx + 1) rep (j, ny + 1) dp[i][j] = 0;

        rep (i, nx)
        {
            rep (j, ny)
            {
                if (x[i] == y[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]);
                }
            }
        }
        cout << dp[nx][ny] << "\n";
    }

    return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

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

C++: #include <iostream>
using namespace std;
static const int INFTY=(1<<21);

int main() {
  std::ios::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  int n;
  cin>>n;
  int p[n+1];
  for (int i=1; i<=n; i++) {
    cin>>p[i-1]>>p[i];
  }
  int m[n+1][n+1];
  for (int i=1; i<=n; i++) {
    m[i][i]=0;
  }
  for (int l=2; l<=n; l++) {
    for (int i=1; i<=n-l+1; i++) {
      int j=i+l-1;
      m[i][j]=INFTY;
      for (int k=i; k<=j-1; k++) {
        m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
      }
    }
  }
  cout<<m[1][n]<<endl;
  return 0;
}

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

static const int N = 1000;

int longestCommonSubsequence(string X, string Y)  {
  int c[N + 1][N + 1];
  int m = X.size();
  int n = Y.size();
  int max1 = 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]);
      }
      max1 = max(max1, c[i][j]);
    }
  }
  return max1;
}
 
int main()  {
  string s1, s2;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)  {
    cin >> s1 >> s2;
  cout << longestCommonSubsequence(s1, s2) << endl;
  }
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    for(int loop = 0; loop < q; ++loop){
        string s, t;
        cin >> s >> t;
        int n1 = s.length(), n2 = t.length();
        vector<vector<int>> dp(n1 + 2, vector<int>(n2 + 2, 0));
        for(int i = 0; i <= n1; ++i){
            for(int j = 0; j <= n2; ++j){
                chmax(dp[i][j + 1], dp[i][j]);
                chmax(dp[i + 1][j], dp[i][j]);
                if(i < n1 && j < n2 && s[i] == t[j]){
                    chmax(dp[i + 1][j + 1], dp[i][j] + 1);
                }
            }
        }
        cout << dp[n1][n2] << '\n';
    }
}

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

using namespace std;

void lcs(string x,string y){
  int m=x.length();
  int n=y.length();
  int c[m+1][n+1];
  for(int i=1;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-1]==y[j-1])
        c[i][j]=c[i-1][j-1]+1;
      else
        c[i][j]=max(c[i-1][j],c[i][j-1]);
    }
  }
  cout << c[m][n] << endl;
}

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