Go: package main

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

type Position struct {
	X int
	Y int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}
	for i := 0; i < n; i++ {
		strX := nextText(sc)
		strY := nextText(sc)
		fmt.Println(calcLcs(strX, strY))
	}
}

func calcLcs(strX, strY string) int {
	return lcs(strX, strY, Position{0, 0}, make(map[Position]int))
}

func lcs(strX string, strY string, position Position, memo map[Position]int) int {
	if position.X >= len(strX) || position.Y >= len(strY) {
		return 0
	}
	if v, ok := memo[position]; ok {
		return v
	}
	if strX[position.X] == strY[position.Y] {
		result := lcs(strX, strY, Position{position.X + 1, position.Y + 1}, memo)
		memo[position] = result + 1
		return memo[position]
	} else {
		result1 := lcs(strX, strY, Position{position.X + 1, position.Y}, memo)
		result2 := lcs(strX, strY, Position{position.X, position.Y + 1}, memo)
		var result int
		if result1 > result2 {
			result = result1
		} else {
			result = result2
		}
		memo[position] = result
		return result
	}
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

C++: #define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <iostream>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <immintrin.h>
#ifdef _MSC_VER
#include <ppl.h>
#endif

using namespace std;

//呪文
#define DUMPOUT std::cerr
#define dump(...) DUMPOUT<<"  ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<std::endl;DUMPOUT<<"    ";dump_func(__VA_ARGS__)

typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const pair<_KTy, _Ty>& m) { o << "{" << m.first << ", " << m.second << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const map<_KTy, _Ty>& m) { if(m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for(auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const unordered_map<_KTy, _Ty>& m) { if(m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for(auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const vector<_Ty>& v) { if(v.empty()) { o << "{ }"; return o; } o << "{" << v.front(); for(auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const set<_Ty>& s) { if(s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for(auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const unordered_set<_Ty>& s) { if(s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for(auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; }	o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const stack<_Ty>& s) { if(s.empty()) { o << "{ }"; return o; } stack<_Ty> t(s); o << "{" << t.top(); t.pop(); while(!t.empty()) { o << ", " << t.top(); t.pop(); } o << "}";	return o; }
template <typename _Ty> ostream& operator << (ostream& o, const list<_Ty>& l) { if(l.empty()) { o << "{ }"; return o; } o << "{" << l.front(); for(auto itr = ++l.begin(); itr != l.end(); ++itr) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& is, pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; }
template <typename _Ty> istream& operator >> (istream& is, vector<_Ty>& v) { for(size_t i = 0; i < v.size(); i++) is >> v[i]; return is; }
namespace aux { // print tuple
  template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
  template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& v) { os << get<N>(v); } };
}
template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys) - 1>::print(os, t); os << "}"; return os; }

template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }

void dump_func() { DUMPOUT << std::endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if(sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); }

template<typename Ty>Ty modpow(Ty n, Ty e, Ty m) { Ty result = 1; while(e > 0) { if(e & 1)result = (result*n) % m; e >>= 1; n = (n*n) % m; }return result; }


#define PI 3.14159265358979323846
#define EPS 1e-10
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(j) (j).begin(), (j).end()
#define SZ(j) ((int)(j).size())
#define fake false



class LCS{
  template<typename T> using V = std::vector<T>;
  bool restorable;

  size_t n, m;
  V<int> s, t;
  V<V<int>> dp;
  V<V<char>> pre;

  void lcs(){
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
      dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
      if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
    }
  }
  void lcsr(){
    // 1: left-up, 2: up, 3: left
    for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++){
      if(s[i-1] == t[j-1]){
        dp[i][j] = dp[i-1][j-1] + 1; pre[i][j] = 1;
      }
      else if(dp[i-1][j] > dp[i][j - 1]){
        dp[i][j] = dp[i-1][j]; pre[i][j] = 2;
      }
      else{
        dp[i][j] = dp[i][j-1]; pre[i][j] = 3;
      }
    }
  }
public:
  LCS(const V<int>& s, const V<int>& t, bool restorable = false)
    : s(s), t(t), n(s.size()), m(t.size()), restorable(restorable)
  {
    dp.resize(n+1, V<int>(m+1, 0));
    if(restorable) {
      pre.resize(n+1, V<char>(m+1, 0));
      lcsr();
    }
    else lcs();
  }
  int length() const {
    return dp[n][m];
  }
  V<int> restore() const {
    assert(restorable);
    V<int> ret;
    size_t i = n, j = m;
    while(i >= 1 && j >= 1){
      if(pre[i][j] == 1){
        ret.push_back(s[i-1]); i--; j--;
      }
      else if(pre[i][j] == 2) i--;
      else j--;
    }
    std::reverse(ret.begin(), ret.end());
    return ret;
  }
};

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

  int q;
  cin >> q;
  REP(i, q) {
    string a, b;
    cin >> a >> b;
    vector<int> va(a.begin(), a.end()), vb(b.begin(), b.end());
    LCS lcs(va, vb, false);
    cout << lcs.length() << endl;
  }

  return 0;
}

C++: #include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <functional>
#include <complex>
#include <cmath>
#include <ccomplex>
using namespace std;

void solve() {
	string x, y;
	cin >> x >> y;
	int xlen = x.length();
	int ylen = y.length();
	int dp[1010][1010];
	dp[0][0] = 0;

	for (int i = 0; i <= xlen; i++) {
		for (int j = 0; j <= ylen; j++) {
			if (i == 0 || j == 0) {
				dp[i + 1][j + 1] = 0;
			}
			else if (x[i - 1] == y[j - 1]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else {
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
			}
		}
	}
	cout << dp[xlen + 1][ylen + 1] << endl;
}
int main() {
	int q;
	cin >> q;
	for (int i = 0; i < q; i++)solve();
}