#include<bits/stdc++.h>
using namespace std;
#define time chrono::system_clock::now().time_since_epoch().count()
mt19937_64 rnd(time);
#define maxn 1000005
#define int long long

int read() {int x;cin>>x;return x;}

void solve() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    vector<int>cnt2(26), cnt1(26);
    for(int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        cnt1[c] ++;
    }
    for(int i = 0; i < m; i++) {
        int c = t[i] - 'a';
        cnt2[c] ++;
    }
    for(int i = 0; i < 26; i++) {
        if(cnt1[i] < cnt2[i]) {
            cout << "0\n";
            return;
        }
        cnt1[i] -= cnt2[i];
    }
    // cout <<"ok\n";
    int ans = 0;
    for(int x = 1; x <= m; x++) {
        int ok = 1;
        vector<int>L(26);
        for(int i = 0; i < 26; i++) {
            int l = (cnt2[i] + x) / (x + 1);
            int r = cnt2[i] / x;
            if(l > r) ok = 0;
            if(ok == 0) break;
            L[i] = l;
        }
        if(ok == 0) continue;
        // cout << "ok" << x << "\n";
        int res = 1e9;
        for(int i = 0; i < 26; i++) {
            if(L[i] == 0) continue;
            res = min(res, cnt1[i] / L[i]);
        }
        ans = max(ans, res + 1);
    }
    cout << ans << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t = read();
    while(t--) solve();
    return 0;
}