Go: package main

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

const max int = 1000 + 1
var A [][]int

func lcs(x, y string) int {
	x = " " + x
	y = " " + y
	for i:=0;i<len(x); i++ {
		for j:=0;j<len(y); j++ {
			A[i][j] = 0
		}
	}
	for i:=1; i<len(x); i++ {
		for j:=1; j<len(y); j++ {
			if x[i] == y[j] {
				A[i][j] = A[i-1][j-1] + 1
			} else if A[i-1][j] > A[i][j-1] {
				A[i][j] = A[i-1][j]
			} else {
				A[i][j] = A[i][j-1]
			}
		}
	}
	return A[len(x)-1][len(y)-1]
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num 
}

func nextStr(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}


func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	A = make([][]int, max)
	for i := range A {
		A[i] = make([]int, max)
	}
	n := nextInt(scanner)
	for i:=0; i<n; i++ {
		x := nextStr(scanner)
		y := nextStr(scanner)
		fmt.Printf("%d\n", lcs(x, y))
	}
}

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();
}