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<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
//#include<utility>
//#include<initializer_list>
//#include<tuple>
//#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
bool isSubstring(string substr, string t) {
	int n = substr.length();
	int seek = 0;
	rep(i, n) {
		bool ex = 0;
		for (int j = seek; j < t.length(); j++) {
			if (substr[i] == t[j]) {
				ex = 1;
				seek = j + 1;
				break;
			}
		}
		if (ex) {
			continue;
		}
		else {
			return false;
		}
	}
	return true;

}

int LongestCommonSubstring(string s, string t) {
	// Wrong plan
	vector<int>dp(s.length(), 0);
	int n = s.length();
	string lcs = "";
	if (isSubstring(s.substr(n - 1, n), t)) {

		dp[n - 1] = 1;
		lcs = s[n - 1];
	}
	for (int i = n - 2; i >= 0; i--) {
		//string substr = s.substr(i, n);
		string substr = s[i] + lcs;
		int issubst = isSubstring(substr, t);
		if (issubst) lcs = substr;
		dp[i] = dp[i + 1] + issubst;
	}
	return dp[0];
}
int LongestCommonSubstring2(string s, string t) {
	vector<vector<int>> dp(s.length() + 1, vector<int>(t.length() + 1, 0));
	int n = s.length() + 1;
	int m = t.length() + 1;
	rep(i, n - 1) {
		rep(j, m - 1) {
			dp[i + 1][j + 1] = s[i] == t[j] ? dp[i][j] + 1 : max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	return dp[n - 1][m - 1];
}
int main() {
	//cout << isSubstring("abc", "abcde") << endl;
	//cout << isSubstring("bd", "abcde") << endl;
	//cout << isSubstring("db", "abcde") << endl;

	//cout << LongestCommonSubstring2("bacd", "becd") << endl;
	//cout << LongestCommonSubstring2("abcd", "becd") << endl;
	//cout << endl;
	cout << LongestCommonSubstring2("a", "a") << endl;
	cout << LongestCommonSubstring2("bbb", "bbb") << endl;
	cout << LongestCommonSubstring2("aba", "bbaba") << endl;
	cout << LongestCommonSubstring2("abababbbaa", "bbabaabba") << endl;
	cout << LongestCommonSubstring2("a", "aaaaa") << endl;
	cout << LongestCommonSubstring2("aizojfeiz", "aaaizojifeizz") << endl;
	cout << LongestCommonSubstring2("zzyiioxizu", "zzsyoizuo") << endl;
	cout << LongestCommonSubstring2("iooooioiooiio", "ooiiioioiooooiioio") << endl;
	cout << LongestCommonSubstring2("ajfoaooieellzljieoaelj", "ajoiiffoaolliseellzljieoaelj") << endl;
	cout << LongestCommonSubstring2("zzzzzyyzyy", "zzyyyyz") << endl;
	cout << LongestCommonSubstring2("abcdef", "fedcba") << endl;
	cout << LongestCommonSubstring2("abc", "xyz") << endl;
	int q;
	cin >> q;
	vector<string> s(q);
	vector<string> t(q);
	rep(i, q) {
		cin >> s[i] >> t[i];
	}
	rep(i, q) {
		cout << LongestCommonSubstring2(s[i], t[i]) << endl;
	}

	return 0;
}

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

int main(){
  int n;
  cin >> n;
  for (int k=0;k<n;k++){
    string x,y;
    cin >> x >> y;
    int p=x.size();
    int q =y.size();
    int l[1001][1001] = {};
    for(int i=1;i<p+1;i++){
      for(int j=1;j<q+1;j++){
	if(x[i-1] == y[j-1] ){
	  l[i][j] = 1+l[i-1][j-1];
	}else{
	  l[i][j]= max(l[i-1][j],l[i][j-1]);
	}
      }
    }
    cout << l[p][q] << endl;
  }
}

C++: #include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1<<30
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define RREP(i,a,b) for(ll i=(a); i>=(b); i--)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> p;
typedef vector<pair<ll, ll>> vpl;


int main(){
    ll q; cin >> q;
    ll dp[1005][1005];
    rep(i,q){
        string a,b; cin >> a >> b;
        ll m = a.size();
        ll n = b.size();
        a = ' ' + a;
        b = ' ' + b;
        rep(i,m+1) dp[i][0] = 0;
        rep(i,n+1) dp[0][i] = 0;
        REP(i,1,m+1){
            REP(j,1,n+1){
                if(a[i] == b[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[m][n] << "\n";
    }
}

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

int lcs_number(string a1, string a2){
	
	int n;
	if (a1.size() <= a2.size())
		n = a1.size() + 1;
	else
		n = a2.size() + 1;

	vector <vector <int> > A(n, vector <int> (n));

	for (int i1=0; i1<n; i1++)
		for (int i2=0; i2<n; i2++)
			if (i1==0 || i2==0)
				A[i1][i2] = 0;

			else if (a1[i1-1] == a2[i2-1])
				A[i1][i2] = A[i1-1][i2-1] + 1;

			else if (A[i1-1][i2] > A[i1][i2-1])
				A[i1][i2] = A[i1-1][i2];

			else
				A[i1][i2] = A[i1][i2-1];

			return A[n-1][n-1];
}

int main(void){
	int n;
	string text1, text2;
	cin>>n;

	for (int i=0; i<n; i++){
		cin>>text1;
		cin>>text2;
		cout<<lcs_number(text1, text2)<<endl;
	}

	return 0;
}

C++: #include<bits/stdc++.h>

using namespace std;


int main() {
    int q;
    cin >> q;

    vector<string> X(q), Y(q);
    int X_size, Y_size;

    vector<int> tmp(3, 0);

    for(int i = 0; i < q; i++) {
        cin >> X[i];
        cin >> Y[i];
    }

    for(int k = 0; k < q; k++) {
        X_size = X[k].size();
        Y_size = Y[k].size();

        // Xのi文字目までとTのj文字目までのLCSの長さdp[i][j]
        vector<vector<int> > dp(X_size+1, vector<int>(Y_size+1, 0));

        // 初期条件
        dp[1][0] = 0, dp[0][1] = 0;

        // dp開始
        for(int i = 1; i <= X_size; i++) {
            for(int j = 1; j <= Y_size; j++) {
                if(X[k][i-1] == Y[k][j-1]) {
                    tmp = {};
                    tmp.push_back(dp[i-1][j-1] + 1);
                    tmp.push_back(dp[i-1][j]);
                    tmp.push_back(dp[i][j-1]);
                    sort(tmp.begin(), tmp.end());
                    dp[i][j] = tmp.back();
                    // dp[i][j] = max({dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1]});
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        cout << dp[X_size][Y_size] << endl;
    }

	return 0;
}