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

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) ((int)(x).size())

typedef double db;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define ws laksdaljk
string s,t;
int n,m;
int ss[26];
int ts[26];
int rs[26];
int ws[26];
void solve() {
    memset(ts,0,sizeof ts);
    memset(ss,0,sizeof ss);
    cin>>s>>t;
    n=s.size(),m=t.size();
    for(char c:s)ss[c-'a']++;
    for(char c:t)ts[c-'a']++;
    int g=ts[0];
    for(int i=1;i<26;i++)g=__gcd(g,ts[i]);
    s=" "+s;
    t=" "+t;
    if(g==1){
        for(int i=0;i<26;i++){
            ws[i]=ts[i]/2;
            rs[i]=ts[i]-ws[i];
        }
        int ans=1e9;
        for(int i=0;i<26;i++){
            if(ss[i]<ws[i])return cout<<"0\n",void();
            if(rs[i]==0)continue;
            ss[i]-=ws[i];
            ans=min(ans,ss[i]/rs[i]);
        }
        cout<<ans<<"\n";
    }
    else{
        for(int i=0;i<26;i++){
            rs[i]=ts[i]/g;
        }
        int ans=1e9;
        for(int i=0;i<26;i++){
            if(rs[i]==0)continue;
            ans=min(ans,max(ss[i]/rs[i]-g+1,0));
        }
        cout<<ans<<"\n";
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}