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 <bits/stdc++.h>
using namespace std;

static const int N = 1000;

int lcs(string X,string Y){
    int c[N+1][N+1];    //c[i][k]???Xi??¨Yk???LCS??¨??????????????????
    int m = X.size();
    int n = Y.size();
    int maxl = 0;
    X = ' ' + X; // X[0]?????????????????\
    Y = ' ' + Y;
    for(int i=1;i<=m;i++) c[i][0] = 0;
    for(int k=1;k<=n;k++) c[0][k] = 0;
    c[0][0] = 0;

    for(int i=1;i<=m;i++){
        for(int k=1;k<=n;k++){
            if(X[i]==Y[k]){
                c[i][k] = c[i-1][k-1] + 1;
            } else {
                c[i][k] = max(c[i-1][k],c[i][k-1]);
            }
            maxl = max(maxl,c[i][k]);
        }
    }

    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<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) {
	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 main() {
	//cout << isSubstring("abc", "abcde") << endl;
	//cout << isSubstring("bd", "abcde") << endl;
	//cout << isSubstring("db", "abcde") << endl;

	//cout << LongestCommonSubstring("bacd", "becd") << endl;
	//cout << LongestCommonSubstring("abcd", "becd") << 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 << LongestCommonSubstring(s[i], t[i]) << endl;
	}

	return 0;
}

C++: #include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
string s1,s2;
int memo[100][100];

int solve(int l1,int l2){
  if(l1 < 0 or l2 < 0)return 0;
  if(memo[l1][l2] >= 0)return memo[l1][l2];
  //cout << s1[l1] << s2[l2] << endl;
  if(s1[l1] == s2[l2]){
    return memo[l1][l2] = solve(l1 - 1,l2 - 1) + 1;
  }
  return memo[l1][l2] = max(solve(l1,l2-1), solve(l1-1,l2));
}
int main(){
  int n;
  cin >> n;
  for(int i = 0;i < n;i++){
    fill(memo[0],memo[100],-1);
    cin >> s1 ;
    cin >> s2;
    cout << solve(s1.length(),s2.length()) - 1 << endl;
  }
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define NIL -1
using namespace std;

int count(const string& X, int i, const string Y, int j,
          vector<vector<int> >& MEMO){
    if (i >= X.size() || j >= Y.size()) return 0;
    if (MEMO[i][j] != NIL) return MEMO[i][j];
    int next_Y = count(X, i    , Y, j + 1, MEMO);
    int next_X = count(X, i + 1, Y, j    , MEMO);
    int max_ = max(next_Y, next_X);
    int j_tmp = j;
    while (X[i] != Y[j_tmp]) {
        j_tmp++;
        if (j_tmp >= Y.size()) return max_;
    }
    int saiyou = count(X, i + 1, Y, j_tmp + 1, MEMO) + 1;
    if (max_ < saiyou) max_ = saiyou;
    return MEMO[i][j] = max_;
}

int main(){
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string X, Y;
        cin >> X >> Y;
        vector<vector<int> > MEMO(X.size(), vector<int>(Y.size(), NIL));
        cout << count(X, 0, Y, 0, MEMO) << endl;
    }
    return 0;
}

C++: /*
** Longest Common Subsequence
*/

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;

const int MAX = 1000 + 5;

char s1[MAX], s2[MAX];
int c[MAX][MAX];

int lcs() {
    int m = strlen(s1);
    int n = strlen(s2);
    c[0][0] = 0;
    int maxl = 0;
    for (int i = 1; i <= m; i++) {
        c[i][0] = 0;
    }
    for (int i = 1; i <= n; i++) {
        c[0][i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i] == s2[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            }
            else if (c[i-1][j] >= c[i][j-1]) {
                c[i][j] = c[i - 1][j];
            }
            else {
                c[i][j] = c[i][j - 1];
            }
            maxl = max(maxl, c[i][j]);
        }
    }

    return maxl;
}

void solve() {
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf("%s %s", s1, s2);
        printf("%d\n", lcs());
    }
}

int main() {
    // freopen("infile", "r", stdin);
    // freopen("outfile", "w", stdout);
    solve();
    return 0;
}