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++: #include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
constexpr int MAX = 1005;
inline void lcs(string X, string Y) {
	vv(int, dp, MAX, MAX, 0);
	int len_X = len(X);
	int len_Y = len(Y);
	rep(i, 0, len_X) {
		rep(j, 0, len_Y) {
			dp[i + 1][j + 1] = (X[i] == Y[j] ? dp[i][j] + 1 : max(dp[i][j + 1], dp[i + 1][j]));
		}
	}
	P(dp[len_X][len_Y]);
}
int main() {
	int n; cin >> n;
	string s1, s2;
	rep(i, 0, n) {
		cin >> s1 >> s2;
		lcs(s1, s2);
	}
	return 0;
}

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

string X;
string Y;

int calc(int x, int y){
    if (X[x] == '\0') return 0;
    int y_ = Y.find(X[x], y);
    if (y_ == string::npos) {
        return 0;
    }
    int ret = 1;
    int tmp1 = calc(x,     y + 1);
    int tmp2 = calc(x + 1, y + 1);
    ret += max(tmp1, tmp2);
    return ret;

    // if (X[x] == '\0') return length;
    // int y_ = Y.find(X[x], y);
    // if (y_ == string::npos) {
    //     if ((Y[y+1] == '\0')) {
    //         return max(length, calc(x_s + 1, x_s + 1, 0, 0));
    //     }
    // }
    // int tmp1 = calc(x_s, x, y + 1, length);
    // int tmp2 = calc(x_s, x + 1, y_ + 1, length + 1);
    // return max(tmp1, tmp2);
}

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

    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int inf = 1e9;
double pi = 3.14159265359;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, b, a) for (int i = a - 1; i >= b; i--)
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dxx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dyy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    int q;
    cin >> q;
    rep (k, 0, q) {
        string s, t;
        cin >> s >> t;
        int sl = s.size(), tl = t.size();
        int dp[sl + 1][tl + 1];
        rep (i, 0, sl + 1) rep (j, 0, tl + 1) dp[i][j] = 0;
        rep (i, 0, sl) {
            rep (j, 0, tl) {
                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], dp[i][j]});
            }
        }
        cout << dp[sl][tl] << "\n";
    }
}

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

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

const int MAX_L=1001;//?????????????????§??????

vector<vector<int> > DP(MAX_L, vector<int>(MAX_L, -1));
string A;//?????????????????????????????????
string B;
string chars;//???????????????????????¨????????????????????????


//A???a???????????¨????????\??????B???b???????????¨????????\??????????????§????????§?????¨????????????????????????????????????
//m?????????????????????????????±??????????????????
int dev(int a, int b){
	if(DP[a][b]<0){
		int maxi= 0;
		//???????????????????????§??????
		for(char c: chars){
			int posa = A.find(c,a);
			int posb = B.find(c,b);
			if(posa>=0 && posb>=0){
				int tmp = dev(posa+1,posb+1);
				maxi = max(maxi, tmp+1);
			}
		}
		DP[a][b]=maxi;
	}
	return DP[a][b];
}

void make_list(){
		//???????????????????????§??????
		for(int c='a'; c<='z'; ++c){
			int posa = A.find(c,0);
			int posb = B.find(c,0);
			if(posa>=0&&posb>=0){
				chars.push_back(c);
			}
		}
		for(int c='A'; c<='Z'; ++c){
			int posa = A.find(c,0);
			int posb = B.find(c,0);
			if(posa>=0&&posb>=0){
				chars.push_back(c);
			}
		}
}

int main(){
	int q;
	cin >> q;
	vector<int> ans(q);
	REP(i,q){
		REP(k,MAX_L){
			REP(l,MAX_L){
				DP[k][l] = -1;
			}
		}
		chars="";
		cin>>A>>B;
		make_list();
		ans[i]=dev(0,0);
	}
	REP(i,q){
		cout<<ans[i]<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <queue>
#include <string>

using namespace std;

const double PI = 3.14159265358979;

int dp[1001][1001];

void lcs(string x, string y) {

	for (int i = 0; i < x.length(); i++) {
		dp[i][0] = 0;
	}
	for (int i = 0; i < y.length(); i++) {
		dp[0][i] = 0;
	}

	for (int i = 1; i <= x.length(); i++) {
		for (int j = 1; j <= y.length(); j++) {

			if (x[i-1] == y[j-1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
}


int main() {

	int n; cin >> n;

	for (int i = 0; i < n; i++)	{
		string big, small;
		cin >> big >> small;
		
		lcs(big, small);
		int res = dp[big.length()][small.length()];
		cout << res << endl;
	}
	

	return 0;
}