#include <bits/stdc++.h>
using namespace std;
/// MACROS
#define int long long
#define itn int
#define str string
#define sz size
#define ll long long
#define ull unsigned long long
#define ld long double
#define ii pair<int, int>
#define fs first
#define sc second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
#define pf push_front
#define fl '\n'
#define el endl
#define eps 1e-12
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define SORT(x) sort(all(x))
#define RSORT(x) sort(rall(x))
#define REV(x) reverse(all(x))
/// FUNCTIONS
const int maxn=100005;
const int maxm=100005;
#define db(x) cerr << #x << ": " << (x) << '\n';
#define lg2(x) __lg(x)
#define pi acos(-1)
#define YN(x) cout << ((x) ? ("YES") : ("NO")) << fl;
#define yn(x) cout << ((x) ? ("Yes") : ("No")) << fl;
#define precision(x) cout.setf(ios::fixed);cout.precision(x);
void print(const auto &v){for(auto it: v)cout<<it<<" ";cout<<fl;}
void printp(const auto &v){for(auto it: v)cout<<it.fs<<" "<<it.sc<<fl;}
vi read(int cnt){vi v(cnt);for(int i=0;i<cnt;i++)cin>>v[i];return v;}
vii readp(int cnt){vii v(cnt);for(int i=0;i<cnt;i++)cin>>v[i].fs>>v[i].sc;return v;}
/////////////////////////////////////////////////////////////////////////////////////
int s[300];
int t[300];
    


void solve(){
    str ss,tt;
    cin>>ss>>tt;   
    for(int i=0;i<300;i++){
        s[i]=t[i]=0;
    }
    for(auto it:ss){
        s[it]++;
    }
    for(auto it:tt){
        t[it]++;
    }

    for(int i='a';i<='z';i++){
        if(s[i]<t[i]){
            cout<<0<<fl;
            return;
        }
    }
    int ans=0;
    for(int k=1;k<=tt.sz();k++){
        int sol=1e9;
        bool can=true;
        for(int i='a';i<='z';i++){
            int p=t[i]/k;
            int r=t[i]%k;
            
            int d=p-r;
            int q=d/(k+1);
            
            p=p-q;
            r=t[i]-p*k;

            if(p==0 || r>p){if(t[i])can=false;continue;}

            // cout<<k<< " "<<(char)i<<" "<<p<<" "<<r<<fl;
            sol=min(sol,  1+ (s[i]-t[i])/p );
        }
        // cout<<k<<" "<<sol<<fl;
        if(sol!=1e9 && can)ans=max(ans,sol);
    }

    cout<<ans<<fl;
}


int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
    return 0;
}