Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const N = 1001

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func lcs(x, y string) int {
	var c [N][N]int
	m := len(x)
	n := len(y)
	var maxl int

	x = " " + x
	y = " " + y

	for i := 1; i <= m; i++ {
		for 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])
			}
			maxl = max(maxl, c[i][j])
		}
	}
	return maxl
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())

	var out bytes.Buffer
	for i := 0; i < q; i++ {
		sc.Scan()
		s1 := sc.Text()
		sc.Scan()
		s2 := sc.Text()
		out.WriteString(fmt.Sprintf("%d\n", lcs(s1, s2)))
	}
	return strings.TrimRight(out.String(), "\n")
}

func main() {
	fmt.Println(answer(os.Stdin))
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)

string str1, str2;
int dp[1001][1001];

void solve()
{
  REP(i, str1.size())
    if(str1[i] == str2[str2.size() - 1])
      dp[i][str2.size() - 1] = 1;
    else
      dp[i][str2.size() - 1] = 0;
  for(int i = str2.size() - 2; i >= 0; i--)
    if(str1[str1.size() - 1] == str2[i])
      dp[str1.size() - 1][i] = 1;
    else
      dp[str1.size() - 1][i] = dp[str1.size() - 1][i + 1];
  for(int i = str1.size() - 2; i >= 0; i--){
    for(int j = str2.size() - 2; j >= 0; j--){
      if(str1[i] == str2[j])
	dp[i][j] = dp[i + 1][j + 1] + 1;
      else
	dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }
}
  
int main()
{
  int q;
  cin >> q;
  cin.ignore();
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    fill(&dp[0][0], &dp[1001][0], -1);
    solve();
    cout << dp[0][0] << endl;
  }
}

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