#include <bits/stdc++.h>
#define MAXN 100005
#define MAXS 1000006
#define MAXT 1003
#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,sn,sm,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);
    sn += n; sm += m;
    if((!n) || !m) { cout << 0 << '\n'; return; }
    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();
        if(sn == 1000000 || sm == 1000) break;
    }
    if(T > 0) while(T--) cout << 0 << '\n';
    return 0;
}