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 <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int MAX_L = 10000;
int q;

string data[MAX_N][2];
ll mem[MAX_L][MAX_L];

ll eval(string &s1, string &s2, int i, int j){
	int ii = i - 1;
	int jj = j - 1;
	if (ii == -1 || jj == -1) return 0;
	if (s1[ii] == s2[jj]) return mem[i - 1][j - 1] + 1;
	if (s1[ii] != s2[jj]) return max(mem[i - 1][j], mem[i][j - 1]);
	throw "exception";
}

ll solve(string s1, string s2){

	int L1 = s1.size();
	int L2 = s2.size();
	rep(i, L1 + 1){
		rep(j, L2 + 1)
		{
			mem[i][j] = eval(s1, s2, i, j);
		}
	}

	return mem[L1][L2];
}

int main() {

	cin >> q;
	rep(i, q){
		cin >> data[i][0];
		cin >> data[i][1];
	}

	rep(i, q){
		cout << solve(data[i][0], data[i][1]) << endl;
	}
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };


struct Combination {

	vector<ll> fact, rfact;

	Combination(ll sz) : fact(sz + 1), rfact(sz + 1) {

		fact[0] = 1;
		for (ll i = 1; i < fact.size(); i++) {
			fact[i] = fact[i - 1] * i % MOD;
		}
		//逆元
		rfact[sz] = inv(fact[sz]);
		for (ll i = sz - 1; i >= 0; i--) {
			rfact[i] = rfact[i + 1] * (i + 1) % MOD;
		}
	}

	ll inv(ll x) {
		//modpow
		return pow(x, MOD - 2);
	}
	ll pow(ll x, ll n) {
		//累乗
		ll ret = 1;
		while (n > 0) {
			if (n & 1) (ret *= x) %= MOD;
			(x *= x) %= MOD;
			n >>= 1;
		}
		return (ret);
	}
	ll P(ll n, ll r) {
		//順列
		if (r < 0 || n < r) return (0);
		return (fact[n] * rfact[n - r] % MOD);
	}

	ll C(ll p, ll q) {
		//組み合わせ
		if (q < 0 || p < q) return (0);
		return (fact[p] * rfact[q] % MOD * rfact[p - q] % MOD);
	}

	ll H(ll n, ll r) {
		//重複組み合わせ
		if (n < 0 || r < 0) return (0);
		return (r == 0 ? 1 : C(n + r - 1, r));
	}
};


/******************************************************************************************/


ll LCS(string& s, string& t) {


	auto dp = make_v<ll>(s.size() + 10, t.size() + 10);
	fill_v(dp, 0);

	for (ll i = 0; i < s.size(); i++) {
		for (ll j = 0; j < t.size(); 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]);
			}
		}
	}
	return dp[s.size()][t.size()];
}


int main() {

	int n;
	cin >> n;
	for (int _ = 0; _ < n; _++)
	{
		string s, t;
		cin >> s >> t;
		cout << LCS(s, t) << endl;
	}

	

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define dump(x)
#define debug(x)
#define dassert(...)
#endif
//#define int long long

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

signed main(){
    int q;
    cin >> q;
    rep(_,0,q) {
        string x, y;
        cin >> x >> y;
        vector<vector<int>> dp(x.size()+1, vector<int>(y.size()+1));
        rep(i,1,x.size()+1) {
            rep(j,1,y.size()+1) {
                dp[i][j] = ((x[i-1] == y[j-1]) ? (dp[i-1][j-1] + 1) : max(dp[i][j-1], dp[i-1][j]));
            }
        }
        cout << dp.back().back() << endl;
    }
}

C++: #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <memory>
#include <string>
#include <map>
using namespace std;
#define MAX 1003

char A[MAX];
char B[MAX];

void print(){}
int DP[MAX][MAX];
int dp(int i,int j){
    if(i<0||j<0) return 0;
    if(DP[i][j]!=-1) return DP[i][j];
    if(A[i]==B[j]) return DP[i][j]=dp(i-1,j-1)+1;
    return DP[i][j]=max(dp(i,j-1),dp(i-1,j));
}
void solve(){


    int tmp;
        scanf("%d",&tmp);
        int r,c;
        while(tmp--){

                scanf("%s%s",A,B);
                r=strlen(A);
                c=strlen(B);
                memset(DP,-1,sizeof(DP));
            printf("%d\n",dp(r-1,c-1));
        }

}

int main(){

    //freopen("in","r",stdin);
    solve();
    return 0;
}

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

using namespace std;
int main(int argc, const char * argv[]) {
    int q, i, m, n, sl1, sl2;
    cin >> q;
    vector<string> strlist;
    string str, str1, str2;
    for(i = 0;i < q;i++){
        cin >> str;
        strlist.push_back(str);
        cin >> str;
        strlist.push_back(str);
    }
    
    //start
    for(i = 0;i < q*2;i += 2){
        str1 = strlist[i];
        sl1 = str1.length();
        str2 = strlist[i+1];
        sl2 = str2.length();
        int dp[sl1+1][sl2+1];
        for(m = 0;m <= sl2;m++){
            dp[0][m] = 0;
        }
        for(m = 0;m <= sl1;m++){
            dp[m][0] = 0;
        }
        for(m = 1;m <= sl1;m++){
            for(n = 1;n <= sl2;n++){
                dp[m][n] = 0;
            }
        }
        for(m = 1;m <= sl1;m++){
            for(n = 1;n <= sl2;n++){
                if(str1[m-1] == str2[n-1]){
                    dp[m][n] = dp[m-1][n-1] + 1;
                }else{
                    dp[m][n] = max(dp[m-1][n], dp[m][n-1]);
                }
            }
        }
        m = sl1;
        n = sl2;
        printf("%d\n", dp[m][n]);
        
    }
    return 0;
}