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++: // Ref : https://book.mynavi.jp/ec/products/detail/id=35408

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

static const int N = 100;;

int main() {
	int n; cin >> n;
	int p[N + 1], m[N + 1][N + 1]; // m_ij is partial LCS between i to j.
	for (int i = 1; i <= n; i++) cin >> p[i - 1] >> p[i];

	for (int i = 1; i <= n; i++) m[i][i] = 0;
	for (int l = 2; l <= n; l++) { // l is a length of partial LCS.
		for (int i = 1; i <= n - l + 1; i++) {
			int j = i + l - 1;
			m[i][j] = INT_MAX;
			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[j] * p[k]);
			}
		}
	}
	cout << m[1][n] << endl;

	return 0;
}

C++: #define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <random>
#include <map>

using namespace std;

int LCS[1010][1010] = {};

int LCSLength(string strX,string strY) {

    int strXSize = strX.length();
    int strYSize = strY.length();
    for (int i = 0; i < strXSize + 1; i++) {
	for (int j = 0; j < strYSize + 1; j++) {
	    if (i == 0 || j == 0) {
		LCS[i][j] = 0;
	    }
	}
    }

    for (int i = 1; i < strXSize + 1; i++) {
	for (int j = 1; j < strYSize + 1; j++) {

	    //LCS[i]==LCS[j]
	    if (strX[i - 1] == strY[j - 1]) {
		LCS[i][j] = LCS[i - 1][j - 1] + 1;
	    }
	    else {
		LCS[i][j] = max(LCS[i][j - 1], LCS[i - 1][j]);
	    }
	}
    }

    return LCS[strXSize][strYSize];
}

int main() {

    //cin.tie(0);
    //ios::sync_with_stdio(false);

    int q; scanf("%d", &q);

    string strX;
    string strY;
    while (q-- > 0) {
	cin >> strX;
	cin >> strY;
	printf("%d\n", LCSLength(strX, strY));
    }



    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[1001][1001];
  int j,k;
  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++){
	ans[j][k]=0;
      }
    }
    for(int j=1;j<=x.size();j++){
      for(int k=1;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 <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), i##_max = (b); i < i##_max; ++i)
#define RFOR(i, a, b) for (int i = (b)-1, i##_min = (a); i >= i##_min; --i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
using vi = vector<int>;
using vd = vector<double>;
using i64 = int64_t;

constexpr int INF = 1 << 30;
constexpr int MOD = 1000000007;

template <typename T>
void print(vector<T> &v) {
  REP(i, v.size()) {
    if (i) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

int main() {
  int n;
  cin >> n;
  string x, y;
  REP(i, n) {
    cin >> x >> y;
    auto xs = x.size();
    auto ys = y.size();
    x = ' ' + x;
    y = ' ' + y;
    vector<vi> dp(xs + 1, vi(ys + 1, 0));
    FOR(xi, 1, xs + 1) {
      FOR(yi, 1, ys + 1) {
        if (x[xi] == y[yi])
          dp[xi][yi] = dp[xi - 1][yi - 1] + 1;
        else
          dp[xi][yi] = max(dp[xi - 1][yi], dp[xi][yi - 1]);
      }
    }
    cout << dp[xs][ys] << endl;
  }
}

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

string S,T;
int x[10000],y[10000];
int dp[10000][10000];
char U[53]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int MAXN;

int main(){
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		MAXN=0;
		cin>>S>>T;
		for(int i=0;i<S.size();i++){
			for(int j=0;j<52;j++){
				if(S[i]==U[j]){
					x[i+1]=j;
				}
			}
		}
		for(int i=0;i<T.size();i++){
			for(int j=0;j<52;j++){
				if(T[i]==U[j]){
					y[i+1]=j;
				}
			}
		}
		for(int i=0;i<=T.size();i++){
			for(int j=0;j<=S.size();j++){
				if(i==0 || j==0){
					dp[i][j]=0;
				}
				else if(x[j]==y[i]){
					dp[i][j]=dp[i-1][j-1]+1;
				}
				else{
					dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
				}
			}
		}
		for(int i=0;i<=T.size();i++){
			for(int j=0;j<=S.size();j++){
				MAXN=max(MAXN,dp[i][j]);
			}
		}
		cout<<MAXN<<endl;
	}
	return 0;
}

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

using namespace std;

string s, t;

int main() {
	int n;
	cin >> n;
	while (n--) {
		//dp[i][j] := s???i??????????????§???t???j??????????????§?????£?????¨??????LCS
		vector<vector<int>> dp(2000, vector<int>(2000));
		cin >> s >> t;
		dp[0][0] = (s[0] == t[0]);
		for (int i = 1; i < s.size(); i++)dp[i][0] = (bool)(dp[0][0] + (s[i] == t[0]));
		for (int j = 1; j < t.size(); j++)dp[0][j] = (bool)(dp[0][0] + (s[0] == t[j]));
		
		for (int i = 1; i < s.size(); i++) {
			for (int j = 1; j < t.size(); j++) {
				if (s[i] == t[j])dp[i][j] = dp[i-1][j-1]+1;
				else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		cout << dp[s.size() - 1][t.size() - 1] << endl;
	}
}

C++: #include <stdio.h>

int score[1010][1010];

int max2 (int a, int b){
  if (a >= b) return a;
  else return b;
}

int len_of_str(const char s[]){
  int num = 0;

  while(s[num]) num++;

  return num;
}


int main() {
  char a[1100];
  char b[1100];
  int datanum;
  scanf("%d",&datanum);
  for(int c = 0; c < datanum; c++){

  scanf("%1100s",a);
  scanf("%1100s",b);
  int num1 = len_of_str(a);
  int num2 = len_of_str(b);


  for(int i = num1; i > 0; i--) a[i] = a[i - 1];
  a[0] = ' ';
  for(int j = num2; j > 0; j--) b[j] = b[j - 1];
  b[0] = ' ';

  for(int i = 0; i <= num1; i++) score[i][0] = 0;
  for(int j = 0; j <= num2; j++) score[0][j] = 0;

  int maximum = 0;

  for(int i = 1; i<= num1; i++){
    for (int j = 1; j <= num2; j++){
      if (a[i] == b[j])score[i][j] = score[i-1][j-1] + 1;
      else if (a[i] != b[j]) score[i][j] = max2(score[i][j-1],score[i-1][j]);
      maximum = max2(maximum,score[i][j]);
    }
  }



  printf("%d\n",maximum);
}
  return 0;
}