#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define mem(a) memset(a,0,sizeof(a))
const int N=100005;
int t,n;
int S[26],T[26];
int check(int x){

    int ans=0;
bool flag=1;
for(int i=0;i<26;i++) if((T[i]+1)/2*x>S[i]) flag=0;
if(flag) return 1; 
    For(cs,1,(n+1)/2)if(1){
        int sum=0,flag=0,gb=1e9;
        For(i,0,25){
            int ab=min(S[i]/x,T[i]/cs),b=T[i]-ab*cs;
            //if(x==2&&cs==1&&i+'a'=='l')cerr<<ab<<" "<<S[i]<<" "<<b<<endl;
            if(b>ab)flag=1;
        }
        //if(x==2&&flag==0)cout<<cs<<" "<<flag<<endl;
        if(flag)continue;
        return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--){
        string s,t;
        cin>>s>>t;
        mem(S); mem(T);
        for(auto i:s)S[i-'a']++;
        for(auto i:t)T[i-'a']++;
        For(i,0,25)S[i]-=T[i];
        int flag=0;
        For(i,0,25)if(S[i]<0){
            cout<<0<<endl; flag=1; break;
        }
        n=t.length();
        if(flag)continue;
        int l=0,r=s.length();
        while(l<r){
            int mid=(l+r)>>1; mid++;
            if(check(mid))l=mid; else r=mid-1;
        }
        cout<<1+l<<"\n";
    }
}