#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define LL long long
string s,t;
LL chars[210],chart[210];
void solve()
{
    LL Ans=0;
    cin>>s>>t;
    fo(i,0,26) chars[i]=chart[i]=0;
    fo(i,0,s.size()-1){ chars[s[i]-'a']++; }
    fo(i,0,t.size()-1){ chart[t[i]-'a']++; }
    fo(i,0,25)
    {
        chars[i]-=chart[i];
        if(chars[i]<0)
        {
            cout<<0<<endl;
            return;
        }
    }
    fo(i,1,s.size()-1)
    {
        bool bb=1;
        fo(k,0,25) 
        {
            if(chart[k]/i<chart[k]%i)
            {
                bb=0;
                break;
            }
        }
        if(bb)
        {
            LL ans=1e9;
            fo(k,0,25) 
            {
                LL req=chart[k]/i;
                while(chart[k]-(req-1)*i<=req-1) req--; 
                if(req) ans=min(ans,chars[k]/req);
            }
            Ans=max(Ans,ans);
        }
    }
    LL ans=1e9;
    fo(k,0,25) 
    {
        LL req=(chart[k]+1)/2;
        if(req) ans=min(ans,chars[k]/req);
    }
    Ans=max(Ans,ans);
    cout<<Ans+1<<endl;
}
int main()
{
    int tcase;
    cin>>tcase;
    while(tcase--) solve();
}