#pragma GCC optimize(2,3,"Ofast","inline")
#include <bits/stdc++.h>
#define int long long
#define double long double
#define lowbit(i) (i&(-i))
#define mid ((l+r)>>1)
using namespace std;
int cnts[26],cntt[26];
void solve(){
	string s; cin>>s;
	string t; cin>>t;
	memset(cnts,0,sizeof(cnts));
	memset(cntt,0,sizeof(cntt));
	for(int i=0;i<s.size();i++) cnts[s[i]-'a']++;
	for(int i=0;i<t.size();i++) cntt[t[i]-'a']++;
	bool ok=1;
	for(int i=0;i<26;i++) if(cntt[i]>cnts[i]) ok=0;
	if(!ok){
		cout<<0<<"\n";
		return ;
	}
	int maxv=1e18;
	for(int i=0;i<26;i++) if(cntt[i]) maxv=min(maxv,cnts[i]/cntt[i]);
	for(int i=0;i<26;i++) cnts[i]-=cntt[i];
//	for(int i=0;i<26;i++) cout<<cnts[i]<<" "; cout<<"\n";
	for(int i=2;i<=t.size();i++){
		int lst[26]; ok=1;
		for(int j=0;j<26;j++){
			int p=cntt[j]/(i-1),q=cntt[j]%(i-1);
			if(q>p){
				ok=0;
				break;
			}
			lst[j]=p-(p-q)/i; 
		}
		if(!ok) continue;
//		cout<<i<<" ";
//		for(int j=0;j<26;j++) cout<<lst[j]<<" ";
		int minv=1e18;
		for(int j=0;j<26;j++) if(lst[j]) minv=min(minv,cnts[j]/lst[j]);
		maxv=max(maxv,minv+1);
	}
	cout<<maxv<<"\n";
}
signed main(){
	int t; cin>>t;
	while(t--) solve();
	return 0;
}