// 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<array<int, 26>> nxt;
string a, b;
int n, m;
int dp[N][N], vis[N][N], id = 0;

int go(int i, int rem) {
    if (!rem) return 0;
    if (i < 0) return n;

    int &res = dp[i][rem];
    if (vis[i][rem] == id) return res;
    vis[i][rem] = id;

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

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

    return res = min(ind, res);
}

void magic() {
    ++id;
    cin >> a >> b;
    n = a.size(), m = b.size();
    nxt.assign(n + 2, {});

    nxt[n].fill(n);
    nxt[n + 1].fill(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;
            return;
        }
    }
}

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