Go: package main

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

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func f() {
	var S, T string
	fmt.Scan(&S)
	fmt.Scan(&T)
	lenS, lenT := len(S), len(T)
	dp := make([][]int, lenS+1)
	for i:=0; i<lenS+1; i++ {
		dp[i] = make([]int, lenT+1)
	}
	for i:=1; i<lenS+1; i++ {
		for j:=1; j<lenT+1; j++ {
			if S[i-1] == T[j-1] {
				dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	fmt.Println(dp[lenS][lenT])
}

func main(){
	var n int 
	fmt.Scan(&n)
	for i:=0; i<n; i++ {
		f()
	}
}

C++: #define DEBUG 1
#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
#define all(v) (v).begin(), (v).end()
#define for1(i, n) for (ll i = 0; i < (n); i++)
#define for2(i, m, n) for (ll i = (m); i < (n); i++)
#define for3(i, m, n, d) for (ll i = (m); i < (n); i += (d))
#define rfor1(i, n) for (ll i = 0; i > (n); i--)
#define rfor2(i, m, n) for (ll i = (m); i > (n); i--)
#define rfor3(i, m, n, d) for (ll i = (m); i > (n); i += (d))
#define INF (1LL << 60)
#define MOD 1000000007LL  // 10**9 + 7
#if DEBUG
#define dump(v1) dump_1(#v1, v1)
#define dump2(v1, v2) dump_2(#v1, v1, #v2, v2)
#define dump3(v1, v2, v3) dump_3(#v1, v1, #v2, v2, #v3, v3)
#define dump4(v1, v2, v3, v4) dump_4(#v1, v1, #v2, v2, #v3, v3, #v4, v4)
#else
#define dump(v1)
#define dump2(v1, v2)
#define dump3(v1, v2, v3)
#define dump4(v1, v2, v3, v4)
#endif
#if DEBUG
template <typename T>
void dump_1(const string& n1, const T& v1)
{
    cerr << n1 << ": " << v1 << endl;
}
template <typename T1, typename T2>
void dump_2(const string& n1, const T1& v1, const string& n2, const T2& v2)
{
    cerr << n1 << ": " << v1 << "  " << n2 << ": " << v2 << endl;
}
template <typename T1, typename T2, typename T3>
void dump_3(const string& n1, const T1& v1, const string& n2, const T2& v2,
            const string& n3, const T3& v3)
{
    cerr << n1 << ": " << v1 << "  " << n2 << ": " << v2 << "  " << n3 << ": "
         << v3 << endl;
}
template <typename T1, typename T2, typename T3, typename T4>
void dump_4(const string& n1, const T1& v1, const string& n2, const T2& v2,
            const string& n3, const T3& v3, const string& n4, const T4& v4)
{
    cerr << n1 << ": " << v1 << "  " << n2 << ": " << v2 << "  " << n3 << ": "
         << v3 << "  " << n4 << ": " << v4 << endl;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& v)
{
    os << "(" << v.first << ", " << v.second << ")";
    return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& v)
{
    os << "(" << get<0>(v) << ", " << get<1>(v) << ", " << get<2>(v) << ")";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    for (auto it = v.begin(); it != v.end(); it++) {
        if (it != v.begin()) {
            os << " ";
        }
        os << *it;
    }
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v)
{
    for (auto it = v.begin(); it != v.end(); it++) {
        if (it != v.begin()) {
            os << " ";
        }
        os << *it;
    }
    return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const map<T1, T2>& v)
{
    os << "{";
    for (auto it = v.begin(); it != v.end(); it++) {
        if (it != v.begin()) {
            os << ", ";
        }
        os << it->first << ":" << it->second;
    }
    os << "}";
    return os;
}
#endif  // DEBUG
void Yes(void) { cout << "Yes" << endl; }
void No(void) { cout << "No" << endl; }
void YES(void) { cout << "YES" << endl; }
void NO(void) { cout << "NO" << endl; }
template <typename T>
void chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
    }
}
template <typename T>
void chmin(T& a, const T& b)
{
    if (a > b) {
        a = b;
    }
}
template <typename T>
void vin(vector<T>& v, ll len)
{
    for1 (i, len) {
        cin >> v[i];
    }
}
template <typename T>
void print(const T& v)
{
    cout << v << endl;
}
//---------------------------------------------------------
ll dp[1001][1001];
void solve()
{
    ll Q;
    cin >> Q;
    vll ans;
    for1 (q, Q) {
        string X, Y;
        cin >> X >> Y;
        ll lenX = X.length();
        ll lenY = Y.length();
        for1 (x, lenX + 1) {
            for1 (y, lenY + 1) {
                dp[x][y] = 0;
                if (x > 0 && y > 0) {
                    if (X[x - 1] == Y[y - 1]) {
                        chmax(dp[x][y], dp[x - 1][y - 1] + 1);
                    }
                }
                if (x > 0) {
                    chmax(dp[x][y], dp[x - 1][y]);
                }
                if (y > 0) {
                    chmax(dp[x][y], dp[x][y - 1]);
                }
            }
        }
        ans.push_back(dp[lenX][lenY]);
    }
    for (ll a : ans) {
        print(a);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

C++: #include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

string s1,s2;
int l[1010][1010];
bool flag[1010][1010];

int L(int i,int j){
	//cout<<i<<" "<<j<<endl;
	if(i<0||j<0){
		return 0;
	}
	else if(s1.at(i)==s2.at(j)){
		if(!flag[i][j]){
			l[i][j]=1+L(i-1,j-1);
			flag[i][j]=true;
		}
		return l[i][j];
	}
	else{
		if(!flag[i][j]){
			int a=L(i,j-1);
			int b=L(i-1,j);
			l[i][j]=a>b?a:b;
			flag[i][j]=true;
		}
		return l[i][j];
	}
}

int main(){
	int q;
	cin>>q;
	for(int i=0; i<q; i++){
		cin>>s1>>s2;
		for(int j=0; j<1010; j++){
			for(int k=0; k<1010; k++){
				flag[j][k]=false;
			}
		}

		cout<<L(s1.size()-1,s2.size()-1)<<endl;
	}
}