#include <bits/stdc++.h>
using namespace std;int fl,tot;
void solve(){
	string s,t;
	cin>>s>>t;
	vector<int> a(26),b(26),d(26);
	for(char&x:s) a[x-'a']++;
	for(char&x:t) b[x-'a']++;
	int mi=t.size(),o=s.size();
	for(int i=0;i<26;i++) if(b[i]) mi=min(mi,b[i]);
	int p=mi,k=s.size();
	for(int i=0;i<26;i++) if(b[i]){
		o=min(o,a[i]/b[i]);
		int c=d[i]=(b[i]+mi)/(mi+1);
		if(c*mi<b[i]) p=mi+1;
		k=min(k,a[i]/c);
	}
	int ans=k-p+1;
	if(p==mi+1){
		int fl=1;
		for(int i=0;i<26;i++) if(a[i]-k*d[i]<b[i]-mi*d[i]) fl=0;
		ans+=fl;
	}
	if(fl){
		if(++tot==2663) cout<<s<<" "<<t<<"\n";
	}else cout<<max(ans,o)<<"\n";
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;fl=t==90522;
	while(t--) solve();
	return 0;
}