#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=2e5+10,V=26;
int T,n,m,a[V],b[V];
char s1[N],s2[N];
int calc(){
	int ans=n,mn=n;
	for(int i=0;i<V;i++)if(b[i]){
		int x=b[i];
		for(;(b[i]+x)/(x+1)>b[i]/x;x--);
		mn=min(mn,x);
	}
	for(int i=0;i<V;i++)if(b[i]){
		if(a[i]<b[i])return 0;
		int x=(b[i]+mn)/(mn+1);
		ans=min(ans,(a[i]-b[i])/x+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",calc());
}
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;
}