#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 = 5e3 + 3 , M = 1e3 + 5;
const int MOD = 1000000007;
const int inf = 1e18;

string s , t;
int n , m;

vector<vector<int>>idx(26);

int mem[N];
int dp(int i , int last){
    if(i == m || last >= n)return 0;

    int &res = mem[i];
    if(~res)return res;

    res = inf;
    //cout << last << ' ';
    auto it = upper_bound(idx[t[i]].begin() , idx[t[i]].end() , last);
    if(it == idx[t[i]].end()){
        res = dp(i + 1 , last);
    }
    else{
        //cout << *it  << ' ';
        res = max(1 + dp(i + 1 , *it) , dp(i + 1 , last));
    }

    return res;
}


void solve() {

    memset(mem , -1 , sizeof mem);

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

    for(auto &c : s){
        c -= 'a';
    }
    for(auto &c : t){
        c -= 'a';
    }

    for(int i = 0 ; i < n ; ++i){
        idx[s[i]].push_back(i);
    }
//    for(int i = 0 ; i < 26 ; ++i){
//        for(auto j : idx[i]){
//            cout << j << ' ';
//        }
//        cout << '\n';
//    }


    cout << dp(0 , 0) << '\n';



}

signed main()
{
    UwU();
    fileIO();
    int test = 1;
    cin >> test;


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

    return 0;
}