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



void solve(){
    string S,T;cin>>S>>T;
    array<int,26>A,B;
    fill(A.begin(),A.end(),0);
    fill(B.begin(),B.end(),0);
    for(auto x:S) A[x-'a']++;
    for(auto x:T) B[x-'a']++;
    int ans=0;
    int mi=1e9;
    for(int i=0;i<26;i++)
    if(B[i]) mi=min(mi,B[i]);
    for(int k=1;k<=mi;k++){
        int isok=1;
        int res=1e9;
        for(int i=0;i<26;i++){
            if(!B[i]) continue;
            int up=(B[i]/k),down=(B[i]-1)/(k+1)+1;
            // cout<<char('a'+i)<<' '<<down<<' '<<up<<'\n';
            if(up<down){
                isok=0;break;
            }
            res=min(res,1+(A[i]-B[i])/down);
        }
        if(!isok) continue;
        ans=max(ans,res);
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int T;cin>>T;
    while(T--) solve();

    return 0;
}
/*
2
bajkaaall aal
abca cba
*/