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

const int N=2e6+3;
string s,t;
int cs[26],ct[26],qt[26],rt[26];
void solve(){
    cin>>s>>t;
    memset(cs,0,sizeof(cs));
    memset(ct,0,sizeof(ct));
    for(char x:s)cs[x-'a']++;
    for(char x:t)ct[x-'a']++;
    vector<int> ms,mt;
    for(int i=0;i<26;++i)if(ct[i]>0){
        ms.push_back(cs[i]);
        mt.push_back(ct[i]);
    }
    int n=mt.size(),m=*min_element(mt.begin(),mt.end());
    int ans=0;
    for(int k=1;k<=m+1;++k){
        int mn=1e9,lst=1,fl=1;
        for(int i=0;i<n;++i){
            qt[i]=(mt[i]+k-1)/k;
            rt[i]=mt[i]-(k-1)*qt[i];
            int qs=ms[i]/qt[i];
            mn=min(mn,qs);
        }
        for(int i=0;i<n;++i){
            int rs=ms[i]-mn*qt[i];
            lst&=rs>=rt[i];
        }
        ans=max(ans,mn-k+1+lst);
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}