//ucup6-m

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll solve(string S,string T){
    vector<ll> cnS(26),cnT(26),neT(26),yoyuu(26);
    for(char c:S) cnS[c-'a']++;
    for(char c:T) cnT[c-'a']++;
    bool f=true;
    ll ans=INF;
    for(int i=0;i<26;i++){
        if(cnS[i]<cnT[i]) f=false;
        if(cnT[i]) chmin(ans,cnS[i]/cnT[i]-1);
        cnS[i]-=cnT[i];
    }
    if(!f){
        return 0LL;
    }
    
    vector<ll> check(si(T));iota(all(check),1);
    shuffle(all(check),rng);
    
    for(ll k:check){
        //cout<<k<<" "<<ans<<endl;
        ll need=(si(T)+k-1)/k,giri=si(T)/k;
        ll sum=0;
        bool f=true;
        for(int i=0;i<26;i++){
            sum+=(cnT[i]+need-1)/need;
            neT[i]=(cnT[i]+need-1)/need;
            yoyuu[i]=cnT[i]/giri-neT[i];
            if(neT[i]*giri>cnT[i]) f=false;
        }
        
        if(!f) continue;
        
        ll X=k-sum;
        if(X<0) continue;
        
        if(X==0){
            ll mi=1LL<<60;
            for(int i=0;i<26;i++){
                if(cnT[i]) chmin(mi,cnS[i]/neT[i]);
            }
            
            chmax(ans,mi);
            
            continue;
        }
        
        if(ans){
            ll can=0;
            for(int i=0;i<26;i++){
                if(yoyuu[i]>0){
                    can+=min(yoyuu[i],max(0LL,cnS[i]/ans-neT[i]));
                    if(cnS[i]/ans-neT[i]<0){
                        can=-1;
                        break;
                    }
                }
                if(cnS[i]/mid-neT[i]<0){
                    can=-1;
                    break;
                }
            }
            if(can<X) continue;
        }
        
        ll left=ans,right=1LL<<28;
        while(right-left>1){
            ll mid=(left+right)/2;
            ll can=0;
            for(int i=0;i<26;i++){
                if(yoyuu[i]>0){
                    can+=min(yoyuu[i],max(0LL,cnS[i]/mid-neT[i]));
                }
                if(cnS[i]/mid-neT[i]<0){
                    can=-1;
                    break;
                }
            }
            //cout<<mid<<" "<<can<<endl;
            if(can>=X) left=mid;
            else right=mid;
        }
        
        chmax(ans,left);
        
    }
    
    return ans+1;
}

ll gutyoku(string S,string T){
    int ans=0;
    sort(all(S));
    sort(all(T));
    
    do{
        sort(all(T));
        do{
            int cn=0;
            for(int i=0;i+si(T)<=si(S);i++){
                if(S.substr(i,si(T))==T) cn++;
            }
            chmax(ans,cn);
        }while(next_permutation(all(T)));
        
    }while(next_permutation(all(S)));
    
    return ans;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    int Q;cin>>Q;
    while(Q--){
        string S,T;cin>>S>>T;
        cout<<solve(S,T)<<"\n";
    }
}

answer.code: In function ‘ll solve(std::string, std::string)’:
answer.code:76:27: error: ‘mid’ was not declared in this scope; did you mean ‘mod’?
   76 |                 if(cnS[i]/mid-neT[i]<0){
      |                           ^~~
      |                           mod