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

int c[30],cc[30],d[30],r[30];
pair<int,int> a[30],b[30];

void solve(){
	string s,t;cin>>s>>t;
	for(int i=0;i<26;i++){
		c[i]=cc[i]=0;
	}
	for(int i=0;i<s.length();i++){
		c[s[i]-'a']++;
	}
	for(int i=0;i<t.length();i++){
		cc[t[i]-'a']++;
	}
	int ok=1;
	for(int i=0;i<26;i++){
		a[i]={c[i],i};
		b[i]={cc[i],i};
		if(cc[i]>c[i]) ok=0;
	}
	if(!ok){
		cout<<"0\n";
		return;
	}
	sort(a,a+26);sort(b,b+26);
	int ans=0;
	for(int k=1;k<=t.length();k++){
		ok=1;int cnt=0,re=0;
		for(int i=0;i<26;i++){
			int e=cc[i]/(t.length()/k);
			r[i]=cc[i]-e*t.length()/k;
			d[i]=e;
			if(e<r[i]) ok=0;
			cnt+=e;re+=r[i];
		}
		if(ok&&((re+cnt*t.length()/k)==t.length())){
			int now=1e9;
			for(int i=0;i<26;i++)if(d[i]){
				now=min(now,c[i]/d[i]);
			}
			int res=now-t.length()/cnt,ck=1;
			for(int i=0;i<26;i++){
				int co=d[i]*now;
				co=c[i]-co;
				if(co<r[i]) ck=0;
			}
//			cout<<now<<" "<<k<<" "<<ck<<" "<<cnt<<endl;
			res+=ck;
			ans=max(ans,res);
		}
	}
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--)
	solve();
	
}