#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e6+5;
string str1,str2;
int cnt1[30],cnt2[30],cnt3[30];
int n,m;

void solve(){
    memset(cnt1,0,sizeof cnt1);
    memset(cnt2,0,sizeof cnt2);
    memset(cnt3,0,sizeof cnt3);
    cin>>str1>>str2;
    n=str1.length(); m=str2.length();
    for(int i=0; i<n; i++) cnt1[str1[i]-'a'+1]++;
    for(int i=0; i<m; i++) cnt2[str2[i]-'a'+1]++;
//    for(int i=1; i<=26; i++) cout<<"cnt2["<<i<<"] = "<<cnt2[i]<<"\n";
    int len=m;
    for(int i=1; i<=m; i++){
        int tot=m/i,res=m%i;
        int res2=0;
        bool flag=1;
        for(int j=1; j<=26; j++){
        	res2+=cnt2[j]%(tot);
        	flag&=((cnt2[j]/tot)>=(cnt2[j]%tot));
		}
//         cout<<"len = "<<i<<" , tot = "<<tot<<" , res = "<<res<<" , res2 = "<<res2<<"\n";
        if(flag && res>=res2 && res%tot==res2%tot){
            len=i; break;
        }
        
    }
//     cout<<"len = "<<len<<"\n";
    {
        int tot=m/len,res=m%len;
        int res2=0;
        for(int i=1; i<=26; i++){
            cnt3[i]=cnt2[i]/tot;
            res2+=cnt2[i]%tot;
        }
        if(res2<res){
            for(int i=1; i<=26; i++){
                while(res2<res && cnt3[i] && (cnt3[i]-1)>=cnt2[i]-(cnt3[i]-1)*tot){
                    cnt3[i]--;
                    res2+=tot;
                }
                if(res2==res) break;
            }
        }
    }
//     for(int i=1; i<=26; i++) cout<<"cnt3["<<i<<"] = "<<cnt3[i]<<"\n";
    int ans=1e9;
    for(int i=1; i<=26; i++){
        if(cnt1[i]<cnt2[i]) { ans=0; break; }
        else if(cnt3[i])
	        ans=min(ans,(cnt1[i]-cnt2[i])/cnt3[i]+1);
    }
    cout<<ans<<"\n";
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}