#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++){
		if(cc[i]>c[i]) ok=0;
	}
	if(!ok){
		cout<<"0\n";
		return;
	}
	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);
			if(r[i]==0){
				while(e>r[i]+t.length()/k) e--,r[i]+=t.length()/k;
			}
			d[i]=e;
			if(e<r[i]||r[i]>t.length()/k) ok=0;
//			cout<<i<<" "<<e<<" "<<r[i]<<" "<<t.length()/k<<endl;
			cnt+=e;re+=r[i];
		}
//		if(cnt>k)
		if(ok&&cnt==k){
			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++)//if(d[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();
	
}