#include <bits/stdc++.h>
#define MAXN 100005
#define MAXS 1000006
#define MAXT 3003
#define For(I,A,B) for(int I = (A), endi = (B); I <= endi; ++I)
#define foR(I,A,B) for(int I = (A), endi = (B); I >= endi; --I)
#define ForE(I,A) for(int I = head[A]; I; I = e[I].nxt)
using namespace std;
typedef long long _ll;
typedef unsigned int ui;
const int INF = 0x7fffffff;

int T,n,m,ans,pos,dp[MAXT][MAXT],nxt[27][MAXS];
char ss[MAXS],tt[MAXT], *s = ss-1, *t = tt-1;
void solve()
{
    cin >> ss >> tt; ans = 0;
    n = strlen(ss); m = strlen(tt);
    For(i,0,n) fill(nxt[i],nxt[i]+26,0);
    For(i,1,m) fill(dp[i],dp[i]+m+1,INF);
    foR(i,n,1)
    {
        For(j,0,25) nxt[j][i-1] = nxt[j][i];
        nxt[s[i]-'a'][i-1] = i;
    }
    For(i,0,m-1) For(j,0,m-1)
    {
        if(dp[i][j] == INF) continue;
        dp[i][j+1] = min(dp[i][j], dp[i][j+1]);
        if(nxt[t[j+1]-'a'][dp[i][j]]) 
            dp[i+1][j+1] = min(dp[i+1][j+1],nxt[t[j+1]-'a'][dp[i][j]]), ans = max(ans,i+1);
    }
    cout << ans << '\n';
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}