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<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
bool isSubstring(string substr, string t) {
	int n = substr.length();
	int seek = 0;
	rep(i, n) {
		bool ex = 0;
		for (int j = seek; j < t.length(); j++) {
			if (substr[i] == t[j]) {
				ex = 1;
				seek = j + 1;
				break;
			}
		}
		if (ex) {
			continue;
		}
		else {
			return false;
		}
	}
	return true;

}

int LongestCommonSubstring(string s, string t) {
	vector<int>dp(s.length(), 0);
	int n = s.length();
	string lcs = "";
	if (isSubstring(s.substr(n - 1, n), t)) {

		dp[n - 1] = 1;
		lcs = s[n - 1];
	}
	for (int i = n - 2; i >= 0; i--) {
		//string substr = s.substr(i, n);
		string substr = s[i] + lcs;
		int issubst = isSubstring(substr, t);
		if (issubst) lcs = substr;
		dp[i] = dp[i + 1] + issubst;
	}
	return dp[0];
}
int main() {
	//cout << isSubstring("abc", "abcde") << endl;
	//cout << isSubstring("bd", "abcde") << endl;
	//cout << isSubstring("db", "abcde") << endl;

	//cout << LongestCommonSubstring("bacd", "becd") << endl;
	//cout << LongestCommonSubstring("abcd", "becd") << endl;
	int q;
	cin >> q;
	vector<string> s(q);
	vector<string> t(q);
	rep(i, q) {
		cin >> s[i] >> t[i];
	}
	rep(i, q) {
		cout << LongestCommonSubstring(s[i], t[i]) << endl;
	}

	return 0;
}

C++: #include <stdint.h>
#include <algorithm>
#include <bitset>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

int dp[1024][1024];

int GetLengthOfLongestCommonSunseq(std::string &a, std::string &b) {
  int max = 0;
  for(int y = 0; y < a.size(); y++){
    for(int x = 0; x < b.size(); x++){
      const int vL = (y > 0) ? dp[y-1][x] : 0;
      const int vU = (x > 0) ? dp[y][x-1] : 0;
      const int vUL = (x > 0 && y > 0) ? dp[y-1][x-1] : 0;
      dp[y][x] = std::max(vL, std::max(vU, vUL + (a[y] == b[x] ? 1 : 0)));
      if(max < dp[y][x]) max = dp[y][x];
    }
  }
  return max;
}

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;
  for(int i = 0; i < n; i++){
    std::string a, b;
    std::cin >> a >> b;
    std::cout << GetLengthOfLongestCommonSunseq(a, b) << std::endl;
  }

  return 0;
}

C++: #include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

string s, t;

int main() {
	int n;
	cin >> n;
	while (n--) {
		//dp[i][j] := s???i??????????????§???t???j??????????????§?????£?????¨??????LCS
		vector<vector<int>> dp(200, vector<int>(200));
		cin >> s >> t;
		dp[0][0] = (s[0] == t[0]);
		for (int i = 1; i < s.size(); i++)dp[i][0] = (s[i] == t[0] || dp[i - 1][0]);
		for (int j = 1; j < t.size(); j++)dp[0][j] = (s[0] == t[j] || dp[0][j - 1]);
		
		for (int i = 1; i < s.size(); i++) {
			for (int j = 1; j < t.size(); j++) {
				if (s[i] == t[j])dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])+1;
				else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		cout << dp[s.size() - 1][t.size() - 1] << endl;
	}
}

C++: #include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	int q;
	cin >> q;
	REP(k, q) {
		string X, Y;
		cin >> X >> Y;
		int x = X.size(), y = Y.size();
		vector<vector<int>> dp(x + 1, vector<int>(y + 1));
		REP(i, x) {
			REP(j, y) {
				if (X[i] != Y[j]) {
					dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
				} else {
					dp[i + 1][j + 1] = dp[i][j] + 1;
				}
			}
		}
		cout << dp[x][y] << endl;
	}

	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll q;
  cin >> q;
  while(q--) {
    string s;
    string t;
    cin >> s >> t;
    mat dp(s.size()+1,vec(t.size()+1));
    for(ll i=0;i<s.size();i++) {
      for(ll j=0;j<t.size();j++) {
        if(s[i]==t[j]) {
          dp[i+1][j+1]=max({dp[i][j]+1,dp[i+1][j],dp[i][j+1]});
        }
        else {
          dp[i+1][j+1]=max({dp[i][j],dp[i+1][j],dp[i][j+1]});
        }
      }
    }
    cout << dp[s.size()][t.size()] << endl;
  }
}

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

int Max(int &a,int b){return a=max(a,b);}

int LCS(string &a,string &b){
  int n = a.size();
  int m = b.size();
  vector <vector<int> > dp(n+1,vector<int>(m+1));

  for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++){
      if(i<n&&j<m&&a[i] == b[j]) Max(dp[i+1][j+1],dp[i][j]+1);
      Max(dp[i+1][j],dp[i][j]);
      Max(dp[i][j+1],dp[i][j]);
    }
  return dp[n][m];
}

int main(){
  int q;
  cin>>q;
  while(q--){
    string a,b;
    cin>>a>>b;
    cout<<LCS(a,b)<<endl;
  }
  return 0;
}