Go: package main

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

var (
	nstr   func() string
	stdout *bufio.Writer
)

func init() {
	nstr = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func main() {
	defer stdout.Flush()

	n := nint()
	xList := make([]string, n)
	yList := make([]string, n)

	for i:=0;i<n ;i++  {
		xList[i] = nstr()
		yList[i] = nstr()
	}

	for i := 0; i<n	; i++  {
		fmt.Println(lcs(xList[i], yList[i]))
	}

}

func lcs(x string, y string) int{
	var m = len(x)
	var n = len(y)

	c := make([][]int, m+1)
	for i:= range c{
		c[i] = make([]int, n+1)
	}
	for i:=	1;i<=m ;i++  {
		for j:=1;j<=n ;j++  {
			if x[i-1] == y[j-1]{
				c[i][j] = c[i-1][j-1] + 1
			}else{
				c[i][j] = int(math.Max(float64(c[i-1][j]), float64(c[i][j-1])))
			}


		}
	}
	return c[m][n]

}


func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func nint64() int64 {
	i, err := strconv.ParseInt(nstr(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func nint() int {
	return int(nint64())
}

func getIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = nint()
	}
	return b
}

func getStringSlice(n int) []string {
	b := make([]string, n)
	for i := 0; i < n; i++ {
		b[i] = nstr()
	}
	return b
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

func contains(s []int, e int) bool {
	for _, a := range s {
		if a == e {
			return true
		}
	}
	return false
}

func bin(i int, prefix bool) string {
	i64 := int64(i)

	if prefix {
		return "0b" + strconv.FormatInt(i64, 2)
	} else {
		return strconv.FormatInt(i64, 2)
	}
}

func strReverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}

	return string(runes)
}

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

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

int solve(string x, string y) {
  int dp[x.size() + 1][y.size() + 1];
  memset(dp, 0, sizeof(dp));
  rep(i, 0, x.size()) {
    rep(j, 0, y.size()) {
      if(x[i] == y[j]) {
        dp[i + 1][j + 1] = dp[i][j] + 1;
      } else {
        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
      }
    }
  }
  return dp[x.size()][y.size()];
}

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

  int q;
  cin >> q;
  vector<int> rsl;
  rep(i, 0, q) {
    string x, y;
    cin >> x >> y;
    rsl.push_back(solve(x, y));
  }
  rep(i, 0, rsl.size()) cout << rsl[i] << endl;
}

C++: #include<iostream>
#include<vector>b
using namespace std;
int main()
{
	int kurikaeshi;
	vector<int> answer;
	cin >> kurikaeshi;
	for (int variable = 0;variable < kurikaeshi;++variable) {
		char X[1024], Y[1024];
		int LX = 0, LY = 0;
		vector<vector<int>> L;
		cin >> X >> Y;
		for (int i = 0;X[i] != 0;++i) LX += 1;
		for (int j = 0;Y[j] != 0;++j) LY += 1;
		L.resize(LX+1);
		for (int k = 0;k < LX + 1;++k) L[k].resize(LY+1);
		for (int i = 0;i<LX+1;++i) {
			for (int j = 0;j<LY+1;++j) {
				if (i == 0 || j == 0) {
					L[i][j] = 0;
				}
				else if (X[i-1] == Y[j-1]) {
					L[i][j] = L[i][j-1] + 1;
				}
				else {
					L[i][j] = L[i-1][j] > L[i][j-1] ? L[i-1][j] : L[i][j-1];
				}
			}
		}
		answer.push_back(L[LX][LY]);
	}
	for (int variable = 0;variable < kurikaeshi;++variable) {
		cout << answer[variable] << endl;
	}
}

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

using namespace std;
using ll = long long;


int main()
{
    int q;
    cin >> q;
    vector<int> ans;

    while(q--) {

        string s, t;
        cin >> s >> t;
        int n = s.size(), m = t.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1)); //dp[i][j] := sのi文字目, tのj文字目まで見た時の最長
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {

                if(s[i] == t[j]) {
                    dp[i + 1][j + 1] = max({dp[i + 1][j], dp[i][j + 1], dp[i][j] + 1});
                }else{
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        ans.push_back(dp[n][m]);
    }
    for(auto i : ans) {
        cout << i << endl;
    }

}

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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
    ll to, rev;
    long double cap;
    Edge(ll _to, long double _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    string s, t;
    cin >> s >> t;
    ll n = s.size();
    ll m = t.size();

    Matrix dp(n + 1, Array(m + 1, 0));

    REP(i, n + 1) {
        REP(j, m + 1) {
            if(i < n)
                chmax(dp[i + 1][j], dp[i][j]);
            if(j < m)
                chmax(dp[i][j + 1], dp[i][j]);
            if(i < n and j < m and s[i] == t[j])
                chmax(dp[i + 1][j + 1], dp[i][j] + 1);
        }
    }
    cout << dp[n][m] << en;
}

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

    //solve();

    ll t;
    cin >> t;
    REP(i, t) { solve(); }

    return 0;
}