#include <fstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <climits>
#include <bits/stdc++.h>
#include <string>
#include <string.h>
#include <math.h>

#define msb(x) (31 - __builtin_clz(x))
#define int long long int
using namespace std;

void fileIO(void) {

#ifndef ONLINE_JUDGE

    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);

#endif

}
int dx[8] = {0,0,1,-1,1,-1,1,-1};
int dy[8] = {1,-1,0,0,1,-1,-1,1};
char pth[4] = {'L','R','U','D'};
int add(int a,int b,int mod){
    return ((a % mod) + (b % mod) ) % mod;
}
int sub(int a,int b,int mod){
    return ((a % mod) - (b % mod) + mod) % mod;
}
int multiply(int a,int b,int mod){
    return ((a % mod) * (b % mod)) % mod;
}
bool equal(double a,double b){
    return abs(a-b) <= 1e-7;
}
bool get_bit(int n , int i){
    return n & (1ll << i);
}
void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int gcd(int x,int y){
    if(!min(x,y))
        return max(x,y);
    return gcd(max(x,y) % min(x,y), min(x,y));
}
int lcm(int x,int y){
    return (x/gcd(x,y)) * y ;
}
int fact(int u){
    if(u == 1)
        return 1;
    return u * fact(u-1);
}
int can(int x,int y){
    return x >= 0 && x < 3 && y >= 0 && y <3;
}
string a,b;
//abcd
//bcda
struct custom_hash{
    size_t operator()(const pair<int,int>&x)const{
        return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
    }
};
unordered_map<pair<int,int>,int,custom_hash>dp;
unordered_map<pair<int,int>,bool,custom_hash>vis;
int f(int i,int curr){
    int ch1=0,ch2=0,ch3=0;
    if(i == a.size() || curr == b.size())
        return 0;
    if(vis[{i,curr}])
        return dp[{i,curr}];
    vis[{i,curr}] = true;
    ch1 = f(i+1,curr);
    ch2 = f(i,curr+1);
    if(a[i] == b[curr])
        ch3 = 1 + f(i+1,curr+1);
    return dp[{i,curr}] = max({ch1,ch2,ch3});
}
void solve() {
    cin >> a >> b;
    dp.clear();vis.clear();
    cout << f(0,0) << '\n';

}

signed main() {
    fastIO();
    fileIO();
    int t;cin>>t;
    while (t--)
        solve();
    return 0;
}