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"
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define IOS std::cin.tie(0),std::ios::sync_with_stdio(false)

namespace idaten {

	using namespace std;
	using ll = int_fast64_t;
	using ull = uint_fast64_t;
	using P = std::pair<int64_t, int64_t>;
	template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
	template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
	template<class Type>struct is_vector : std::false_type {};
	template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
	template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
		if (v.empty())return out;
		constexpr bool is_vector_v = is_vector<T>::value;
		if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
		else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
		return out;
	}
	inline void put() {}
	template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
	template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
	inline void putn() {}
	template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

	void solve() {
		IOS;
		int q;
		cin >> q;
		REP(loop, q) {
			string x, y;
			cin >> x >> y;
			int m = x.size(), n = y.size();
			vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
			REP(i, m) {
				REP(j, n) {
					dp[i + 1][j + 1] = max({ dp[i + 1][j],dp[i][j + 1],dp[i][j] + (x[i] == y[j]) });
				}
			}
			put(dp[m][n]);
		}
	}
} // namespace idaten

int main() {
	idaten::solve();
	return 0;
}

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;

//A???a???????????¨????????\??????B???b???????????¨????????\??????????????§????????§?????¨????????????????????????????????????
//m?????????????????????????????±??????????????????
int dev(int a, int b){
	if(DP[a][b]<0){
		int maxi= 0;
		//???????????????????????§??????
		for(int c='A'; c<='Z'; ++c){
			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];
}

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;
			}
		}
		cin>>A>>B;
		ans[i]=dev(0,0);
	}
	REP(i,q){
		cout<<ans[i]<<endl;
	}
	return 0;
}

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

const int N = 1e4 + 10;
long long n, q, m, tmp;
long long dp[N][N];
string s, p;
string a1, a2;

int main() 
{
	cin >> q;
	for (int x = 0; x < q; x++) {
	cin >> a1 >> a2;
	if (a1.size() > a2.size())
		s = a1, p = a2;
	else
		p = a1, s = a2;
	n = s.size();
	m = p.size();
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if(s[i] == p[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[i + 1][j + 1] << '\n';
		}
	}
	cout << dp[n][m] << '\n';
	}
	return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
usig namespace std;
static const int N=1000;
int lcs(string X,string Y){
  int c[N+1][N+1];
  int m=X.size();
  int n=Y.size();
  int maxl=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{
        c[i][j]=max(c[i-1][j],c[i][j-1]);
        }  
      maxl=max(maxl,c[i][j]);
     }
   }
  return maxl;
}

int main(){
 
string s1,s2;
int n;cin>>n;
for(int i=0;i<n;i++){
cin>>s1>>s2;
cout<<lcs(s1,s2)<<endl;
}
return 0;
 
}

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

#define _CRT_SECURE_NO_WARNINGS

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1; i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

const int INF = 1000000000;
const double PI = 3.1415926535897932384626433832795;

// N, E, S, W
const int dx[4] = { -1, 0,  1,  0 };
const int dy[4] = { 0, 1,  0, -1 };

using LL = long long int;
using LD = long double;
using pii = pair<int, int>;
using pdd = pair<double, double>;
using pll = pair<LL, LL>;
using vi = vector<int>;
using vd = vector<double>;
using vvi = vector<vi>;
using vll = vector<LL>;

//==============================================
vvi dp(1050, vi(1050));

int lcs(string x, string y) {
	int ans = 0;
	int m = x.size();
	int n = y.size();

	x = ' ' + x;
	y = ' ' + y;
	REP3(i, 1, m) {
		REP3(j, 1, n) {
			if (x[i] == y[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			} else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
			ans = max(ans, dp[i][j]);
		}
	}

	return ans;
}

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

	int q;
	cin >> q;

	string str1, str2;
	REP(i, q) {
		cin >> str1 >> str2;
		cout << lcs(str1, str2) << "\n";
	}
	return 0;
}