// Author: _Sherbiny

#include "bits/stdc++.h"

#ifdef DBG

#include "./debug.h"

#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
#define endl '\n'
///////////////////////////////////
const int oo = 2e9, N = 1001;
vector<vector<int>> nxt;
string a, b;
int n, m;
int dp[N][N];
vector<vector<bool>>vis;

int go(int i, int sz) {
    if (!sz) return -1;
    if (i < 0) return n;

    int &res = dp[i][sz];
    if (vis[i][sz]) return res;
    vis[i][sz] = true;

    res = go(i - 1, sz);
    int ind = go(i - 1, sz - 1);

    ind = nxt[ind + 1][b[i] - 'a'];

    return res = min(ind, res);
}

void magic() {
    cin >> a >> b;
    n = a.size(), m = b.size();

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


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


    for (int sz = m; sz >= 0; --sz) {
        if (go(m - 1, sz) < n) {
            cout << sz << endl;
            return;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) magic();
}