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

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t_;
    cin>>t_;
    while(t_--){
        string s, t;
        cin>>s>>t;
        vector<int>fs(26), ft(26);
        int n = (int)s.size(), m = (int)t.size();
        for(char ch : s) fs[ch - 'a']++;
        for(char ch : t) ft[ch - 'a']++;
        bool w = true;
        for(int j=0;j<26;j++){
            if(fs[j] < ft[j]) w = false;
        }
        if(!w){
            cout<<"0\n";
            continue;
        }
        int ans = 0;
        for(int k=1;k<=m;k++){
            vector<int>ct(26), rt(26);

            bool ok = true;
            for(int j=0;j<26;j++){
                ct[j] = (ft[j] + k - 1) / k;
                rt[j] = ft[j] - ct[j] * (k - 1); 
                if( rt[j] < 0) ok = false;
            }
            if(!ok) break;
            int cnt = n;
            bool one_more = true;
            for(int j=0;j<26;j++){
                if(!ct[j]) continue;
                int c = (fs[j] - ft[j]) / ct[j] + 1;
                cnt = min(cnt, c);
            }
            ans = max(ans, cnt);
        }
        cout<<ans<<"\n";
    }
    return 0;
}