#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']++;
        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] > ct[j] || 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] / ct[j];
                cnt = min(cnt, c);
            }
            if(cnt < k - 1) continue;
            for(int j=0;j<26;j++){
                int r = fs[j] - cnt * ct[j];
                if(r < rt[j]) one_more = false;
            }
            int cur = cnt - (k - 1);
            if(one_more) cur++;
            ans = max(ans, cur);
        }
        cout<<ans<<"\n";
    }
    return 0;
}