#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T> &x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int i=1,len=x.size();i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<endl;
}
template<typename T,typename ... S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
const int N=2e6+10,V=26;
int T,n,m,a[V],b[V];
char s1[N],s2[N];
int calc1(){
	int ans=n;
	for(int i=0;i<V;i++)if(b[i]){
		if(a[i]<b[i])return 0;
		ans=min(ans,(a[i]-b[i])/((b[i]+1)/2)+1);
	}
	return ans;
}
int calc2(){
	int ans=n,g=0;
	for(int i=0;i<V;i++)g=__gcd(g,b[i]);
	for(int i=0;i<V;i++)if(b[i]){
		if(a[i]<b[i])return 0;
		ans=min(ans,(a[i]-b[i])/(b[i]/g)+1);
	}
	return ans;
}
void get(){
	scanf("%s%s",s1+1,s2+1),n=strlen(s1+1),m=strlen(s2+1);
	for(int i=1;i<=n;i++)a[s1[i]-'a']++;
	for(int i=1;i<=m;i++)b[s2[i]-'a']++;
	printf("%d\n",max(calc1(),calc2()));
}
void clr(){
	for(int i=0;i<V;i++)a[i]=b[i]=0;
}
int main(){
	for(scanf("%d",&T);T--;clr())get();
	return 0;
}