#include<bits/stdc++.h>
using namespace std;
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        string s,t;cin>>s>>t;
        int cs[26]={},ct[26]={};
        for(auto x:s) cs[x-'a']++;
        for(auto x:t) ct[x-'a']++;
        int mn=1e9,ans=0;
        for(int w:ct)if(w) mn=min(mn,w);bool ff=0;
        for(int i=0;i<26;i++)if(cs[i]<ct[i]) ff=1;
        if(ff){puts("0");continue;}
        for(int i=0;i<=mn;i++){
            int res=1e9;
            for(int j=0;j<26;j++)if(ct[j]){
                int p=(ct[j]+i)/(i+1);
                res=min(res,(cs[j]-ct[j])/p);
            }
            ans=max(ans,res);
        }
        cout<<ans+1<<' ';cout<<'\n';
    }
}