#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())

const int C=26;
int a[C],b[C];

void ahcorz(){
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    {
        string s,t; cin >> s >> t;
        for(auto c: s) a[c-'a']++;
        for(auto c: t) b[c-'a']++;
    }
    int mn=1e9;
    for(int i=0; i<C; ++i) if(b[i]) mn=min(mn,a[i]/b[i]);
    int res=mn;
    int n=accumulate(b,b+C,0);
    for(int k=1; k<=n; ++k){
        mn=1e9;
        for(int i=0; i<C; ++i) if(b[i]){
            int x=(b[i]+k)/(k+1);
            if(b[i]-x*k<0){
                mn=0;
                break;
            }
            mn=min(mn,a[i]/x);
        }
        res=max(res,mn);
    }
    cout << res << "\n";
}

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