#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e6+5;
string str1,str2;
int cnt1[30],cnt2[30],cnt3[30];
int n,m;

void solve(){
    memset(cnt1,0,sizeof cnt1);
    memset(cnt2,0,sizeof cnt2);
    memset(cnt3,0,sizeof cnt3);
    cin>>str1>>str2;
    n=str1.length(); m=str2.length();
    for(int i=0; i<n; i++) cnt1[str1[i]-'a'+1]++;
    for(int i=0; i<m; i++) cnt2[str2[i]-'a'+1]++;
    // for(int i=1; i<=26; i++) cout<<"cnt2["<<i<<"] = "<<cnt2[i]<<"\n";
    int len=m;
    for(int i=1; i<=m; i++){
        int tot=m/i,res=m%i;
        int res2=0;
        for(int j=1; j<=26; j++) res2+=cnt2[j]%(tot);
        // cout<<"len = "<<i<<" , res = "<<res<<" , res2 = "<<res2<<"\n";
        if(res>=res2 && res%tot==res2%tot){
            len=i; break;
        }
        
    }
    // cout<<"len = "<<len<<"\n";
    {
        int tot=m/len,res=m%len;
        int res2=0;
        for(int i=1; i<=26; i++){
            cnt3[i]=cnt2[i]/tot;
            res2+=cnt2[i]%tot;
        }
        if(res2<res){
            for(int i=1; i<=26; i++){
                while(res2<res && cnt3[i] && (cnt3[i]-1)>cnt2[i]-(cnt3[i]-1)*tot){
                    cnt3[i]--;
                    res2+=tot;
                }
                if(res2==res) break;
            }
        }
    }
    // for(int i=1; i<=26; i++) cout<<"cnt3["<<i<<"] = "<<cnt3[i]<<"\n";
    int ans=-1;
    for(int i=1; i<=26; i++){
        if(cnt1[i]<cnt2[i]) { ans=0; break; }
    }
    if(!ans){
        cout<<"0\n";
        return;
    }
    ans=1;
    int res=1e9;
    for(int i=1; i<=26; i++) if(cnt3[i])
        res=min(res,(cnt1[i]-cnt2[i])/cnt3[i]);
    cout<<ans+res<<"\n";
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}