Go: package main

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

const max int = 1000 + 1
var A [][]int

func lcs(x, y string) int {
	x = " " + x
	y = " " + y
	for i:=0;i<len(x); i++ {
		for j:=0;j<len(y); j++ {
			A[i][j] = 0
		}
	}
	for i:=1; i<len(x); i++ {
		for j:=1; j<len(y); j++ {
			if x[i] == y[j] {
				A[i][j] = A[i-1][j-1] + 1
			} else if A[i-1][j] > A[i][j-1] {
				A[i][j] = A[i-1][j]
			} else {
				A[i][j] = A[i][j-1]
			}
		}
	}
	return A[len(x)-1][len(y)-1]
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num 
}

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


func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	A = make([][]int, max)
	for i := range A {
		A[i] = make([]int, max)
	}
	n := nextInt(scanner)
	for i:=0; i<n; i++ {
		x := nextStr(scanner)
		y := nextStr(scanner)
		fmt.Printf("%d\n", lcs(x, y))
	}
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>

#define SIZE 1002
int Table[SIZE][SIZE];
char a[SIZE];
char b[SIZE];
int n1;
int n2;

int Count(int i, int j)
{
    if(i == 0 || j == 0) return 0;
    if(a[i-1] == b[j-1]){
        return Table[i-1][j-1] + 1;
    }
    return std::max(Table[i-1][j], Table[i][j-1]);
}
int Solve()
{
    n1 = std::strlen(a);
    n2 = std::strlen(b);
    for(std::size_t i = 1; i < n1; ++i){
        for(std::size_t j = 1; j < n2; ++j){
            Table[i][j] = Count(i, j);
        }
    }
    return Table[n1-1][n2-1];
    
}

int main()
{
    int n;
    std::scanf("%d\n", &n);
    for(int i = 0; i < n; ++i){
        std::fgets(a, SIZE, stdin);
        std::fgets(b, SIZE, stdin);
        std::printf("%d\n", Solve());
    }
    return 0;
}

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