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++: #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;
}