#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
typedef long long ll;
typedef pair<int,int> PII;
ll n,n1,n2;
char s1[N],s2[N];
int cnt1[30],cnt2[30],ccnt1[30];
int cntneed[30];
int mx[30];

bool check(int c1[],int c2[]){
    for(int i=0;i<26;i++){
        if(c1[i]<c2[i]) return false;
        c1[i]-=c2[i];
    }
    return true;
}

bool cmp(int leave){

    for(int i=0;i<26;i++){
        leave-=max(cntneed[i]-mx[i],0);

    }
    return leave>=0;
}


bool Check(int mid){
    // cout<<"--"<<mid<<endl;
    memset(mx,0,sizeof mx);
    int tot=0;
    for(int i=0;i<26;i++){
        // if(cnt1[i]<mid) return false;
        mx[i]=cnt1[i]/mid;
        tot+=cnt1[i];
    }
    if(tot<n2*mid) return false;
    // for(int i=0;i<26;i++) cout<<mx[i]<<" ";
    // cout<<endl;
    bool flag=1;
    for(int i=0;i<26;i++){
        if((cnt2[i]+1)/2>mx[i]) flag=0;
    }
    if(flag) return true;
    for(int border=n2-1;border>=(n2+1)/2;border--){
        // cout<<"--"<<" "<<border<<endl;
        int cha=n2-border;
        int val=n2/cha;
        int cntmod=n2%cha,cnt=cha-cntmod;
        vector<PII> v;
        for(int i=0;i<26;i++) ccnt1[i]=cnt1[i];
        memset(cntneed,0,sizeof cntneed);
        bool flg=1;
        for(int i=0;i<26;i++){
            int x=ccnt1[i],y=i;
            int t=x%val;
            // cout<<x<<" "<<y<<" "<<t*(val+1)<<endl;
            if(t*(val+1)>x){
                flg=0;
                break;
            }
            x-=t*(val+1);
            cntneed[y]+=t;
            cntmod-=t;
            if(cntmod<0){
                flg=0;
                break;
            }
            ccnt1[i]=x;
        }
        // cout<<"--"<<border<<endl;
        if(!flg) continue;
        int leave=cntmod/val;
        for(int i=0;i<26;i++) cntneed[i]+=ccnt1[i]/val;
        if(cmp(leave)){
            // cout<<"--"<<border<<endl;
            // for(int i=0;i<26;i++) cout<<cntneed[i]<<" ";
            // cout<<endl;
             return true;
        }
    }
    return false;
}

void HuangGuangsheng(){
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    n1=strlen(s1+1),n2=strlen(s2+1);
    memset(cnt1,0,sizeof cnt1);
    memset(cnt2,0,sizeof cnt2);
    memset(cntneed,0,sizeof cntneed);
    for(int i=1;i<=n1;i++) cnt1[s1[i]-'a']++;
    for(int i=1;i<=n2;i++) cnt2[s2[i]-'a']++;
    for(int i=0;i<26;i++) cntneed[i]=(cnt2[i]+1)/2;
    int ans=0;
    if(check(cnt1,cnt2)) ans++;
    else{
        puts("0");
        return;
    }
    ll l=1,r=n1;
    ll tot=0;
    
    if(!Check(1)){
        puts("1");
        return;
    }
    // Check(6);
    while(l<r){
        ll mid=l+r+1>>1;
        if(Check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%lld\n",l+1);
}

int main(){
    int hgs;
    cin>>hgs;
    while(hgs--){
        HuangGuangsheng();
    }
}