Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	for i := 0; i < n; i++ {
		x := getNextString(scanner)
		y := getNextString(scanner)

		fmt.Fprintln(writer, lcs(x, y))
	}

	writer.Flush()
}

func lcs(x, y string) int {
	lx := len(x)
	ly := len(y)
	dp := make([][]int, lx+1)
	for i := 0; i <= lx; i++ {
		dp[i] = make([]int, ly+1)
	}
	for i := 0; i < lx; i++ {
		for ii := 0; ii < ly; ii++ {
			if x[i] == y[ii] {
				dp[i+1][ii+1] = dp[i][ii] + 1
				continue
			}
			dp[i+1][ii+1] = dp[i][ii+1]
			if dp[i+1][ii] > dp[i+1][ii+1] {
				dp[i+1][ii+1] = dp[i+1][ii]
			}
		}
	}
	return dp[lx][ly]
}

C++: #include <iostream>

using namespace std;

int lcs(string X, string Y) {
  int memo[1010][1010];
  int maxl = 0;

  // 初期化、境界条件を考慮して場合分け
  for (int i = 0; i < X.size(); i++) {
    if (X[i] == Y[0]) {
      memo[i][0] = 1;
    } else {
      memo[i][0] = 0;
    }
    maxl = max(maxl, memo[i][0]);
  }

  for (int j = 0; j < Y.size(); j++) {
    if (X[0] == Y[j]) {
      memo[0][j] = 1;
    } else {
      memo[0][j] = 0;
    }
    maxl = max(maxl, memo[0][j]);
  }

  // cout << memo[0][0] << endl;
  // cout << "--------------" << endl;

  for (int i = 1; i < X.size(); i++) {
    for (int j = 1; j < Y.size(); j++) {
      if (X[i] == Y[j]) {
        memo[i][j] = memo[i-1][j-1] + 1;
      } else {
        memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
      }
      maxl = max(maxl, memo[i][j]);
      //cout << i << "," << j << "," << X[i] << "," << Y[j] << "," << maxl << endl;
    }
  }
  return maxl;
}

int main() {
  int q; cin >> q;
  for (int i = 0; i < q; i++) {
    string X, Y; cin >> X >> Y;
    //cout << endl;
    cout << lcs(X, Y) << endl;
  }
}

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

using namespace std;

int main() {
    int Q = 0;
    string X,Y;
    cin>>Q;
    for (int q = 0; q < Q; q++) {
        cin>>X>>Y;

        int len[1001][1001] = {};
        for (int s = 1; s <= X.length(); s++) {
            for (int t = 1; t <= Y.length(); t++) {
                if (X[s-1] == Y[t-1]) len[s][t] = 1 + len[s-1][t-1];
                else len[s][t] = max(len[s-1][t], len[s][t-1]);
            }
        }
        cout<<len[X.length()][Y.length()]<<endl;
    }
}

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

int c[MAX][MAX];
int lcs(string x, string y)
{
    int m = x.size();
    int n = y.size();
    int max1 = 0;
    x = ' '+x;
    y = ' '+y;
    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] == y[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];
        }
    }
}
int main()
{
    int n, t;
    string s1, s2;
    cin >> n;
    while(n--)
    {
        cin >> s1 >> s2;
        lcs(s1,s2);
        cout << c[s1.size()][s2.size()] << endl;
    }
    return 0;
}

C++: #include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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;
}

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

ll dp[1010][1010];

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

	ll q;
	cin >> q;
	while (q--) {
		string x, y;
		cin >> x >> y;
		memset(dp, 0, sizeof(dp));
		
		REP(i, x.size()) {
			REP(j, y.size()) {
				if (x[i] == y[j]) {
					chmax(dp[i + 1][j + 1], dp[i][j] + 1);
				}
				chmax(dp[i + 1][j + 1], dp[i + 1][j]);
				chmax(dp[i + 1][j + 1], dp[i][j + 1]);
			}
		}

		cout << dp[x.size()][y.size()] << endl;
	}

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
#define ALL(x) x.begin(),x.end()
typedef pair<int, int> P;
typedef long long ll;

int N;
string s,t;
int dp[1001][1001];

// int solve(int i, int j) {
//
//     if (dp[i][j] >= 0) {
//         return dp[i][j];
//     }
//
//     int res;
//     if (i >= n || j >= m) {
//         res = 0;
//     }
//     else if (s[i] == t[j]) {
//         res = solve(i+1, j+1) + 1;
//     }
//     else {
//         res = max(solve(i+1, j), solve(i, j+1));
//     }
//     return dp[i][j] = res;
// }

int main() {
    cin >> N;
    while (N--) {
        cin >> s >> t;
        int n = s.size(), m = t.size();
        fill(dp[0], dp[1001], 0);
        for (int i=0;i<n;++i) {
            for (int j=0;j<m;++j) {
                if (s[i] == t[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[n][m] << endl;
    }
}

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

int N,len1,len2;
string seq1,seq2;
int dp[1000][1000];

int main() {
	cin >> N;
	for (int M=0; M<N; M++){
		cin >> seq1 >> seq2;
		len1 = seq1.length();
		len2 = seq2.length();
		for (int i=1; i<=len1; i++){
			for (int j=1; j<=len2; j++){
				if (seq1[i-1] == seq2[j-1]){
					dp[i][j] = dp[i-1][j-1] + 1;
				}else if (dp[i][j-1] > dp[i-1][j]){
					dp[i][j] = dp[i][j-1];
				}else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		cout << dp[len1][len2] << endl;
	}
	
	return 0;
}