#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
#define eb emplace_back
using ll=long long;
using PL=pair<ll,int>;
using P=pair<int,int>;
#define tct template<class t>
#define tctu template<class t,class u>
tct using vc=vector<t>;
tctu bool chmax(t&a,u b){if(a<b){a=b;return 1;}return 0;}
tctu bool chmin(t&a,u b){if(a>b){a=b;return 1;}return 0;}

const int ALP=26;
void solve(){
	string S,T;
	cin>>S>>T;
	vc<int> A(ALP),B(ALP);
	for(int i=0;i<S.size();i++) A[S[i]-'a']++;
	for(int i=0;i<T.size();i++) B[T[i]-'a']++;
	for(int i=0;i<ALP;i++){
		if(A[i]<B[i]){
			puts("0");
			return;
		}
	}
	vc<int> cand;
	int bef=-1;
	for(int i=1;i<=T.size();i++){
		int d=T.size()/i;
		if(d!=bef){
			//printf("* %d\n",d);
			cand.pb(d);
			bef=d;
		}
	}
	auto check=[&](int d)->bool{
		//printf("%d\n",d);
		for(int i=0;i<cand.size();i++){
			int l=cand[i];
			bool up=true;
			for(int j=0;j<ALP;j++){
				int s=(B[j]+l)/(l+1),t=B[j]/l;
				up&=(s<=t&&s<=(A[j]-B[j])/(d-1));
			}
			if(up) return true;
		}
		return false;
	};
	int l=1,r=S.size()+1;
	while(r-l>1){
		int d=(l+r)/2;
		if(check(d)) l=d;
		else r=d;
	}
	cout<<l<<endl;
}
	
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int T;
	cin>>T;
	while(T--) solve();
}