#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long int


void UwU(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}


void fileIO(void) {

#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
}

int dx_all[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy_all[8] = {0, 1, 0, -1, -1, 1, -1, 1};
char di[]  = {'R' , 'L' , 'U' , 'D'};
int  dx[]  = { 1  , -1  ,  0  ,  0};
int  dy[]  = { 0  , 0   ,  -1 ,  1};

const double pi = 3.14159265358979323846;
const int N = 1001 , M = 7;
const int MOD = 1000000007;
const int inf = 1e18;

int n , m;
string s , t;
vector<vector<int>>nxt;
int mem[N][N];
vector<vector<bool>>vis;
int dp(int idx , int sz){

    if(!sz) return -1;
    if(idx < 0)return n;

    int &res = mem[idx][sz];
    if(vis[idx][sz])return res;

    vis[idx][sz] = true;

    int leave= dp(idx - 1 , sz);
    int take = dp(idx - 1 , sz - 1);

    take = nxt[take + 1][t[idx] - 'a'];
    return res = min(take , leave);
}


void solve() {

    //memset(mem , -1 , sizeof mem);

    cin >> s >> t;
    n = s.size();
    m = t.size();

    vis.assign(N , vector<bool>(N , false));
    nxt.assign(n + 2 , vector<int>(26 , n));

    for (int i = n - 1 ; i >= 0; --i) {
        nxt[i] = nxt[i + 1];
        nxt[i][s[i] - 'a'] = i;
    }

    for(int i = m  ; i >= 0 ; --i){
        if(dp(m - 1 , i) < n){
            cout << i << '\n';
            return;
        }
    }

}

signed main()
{

    UwU();
    fileIO();
    int test = 1;
    cin >> test;


    while(test--) {
        solve();
    }

    return 0;
}