#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

vi getcnt(string s){
	vi cnt(26);
	rep(i,sz(s)) cnt[s[i]-'a']+=1;
	return cnt;
}

void slv(){
	string s,t;
	cin>>s>>t;
	int n=sz(s),m=sz(t);
	vi cnts=getcnt(s);
	vi cntt=getcnt(t);

	const int si=26;
	rep(i,si){
		if(cnts[i]<cntt[i]){
			print(0);
			return;
		}
	}

	int ans=0;
	rng(p,1,m+1){
		int pok=1;
		int blocks=m/p;
		int chunk=m%p;
		int now=0;
		int losun=0,can=0;
		rep(i,si){
			if(!cntt[i]) continue;
			int r=cntt[i]%blocks;
			int x=cntt[i]/blocks;
			if(x<r) pok=0;
			now+=r;
			int hi=x;
			// x >= cntt[i] - x * blocks 
			// x*(blocs+1)>=cntt[i]
			int lo=cntt[i]/(blocks+1);
			// in pattern i occurs in range [lo ... hi]
			losun+=lo;
			can+=hi-lo;
		}
		if(!pok) continue;
		int leftover=chunk-now;
		if(leftover<0 or leftover%blocks) continue;
		leftover/=blocks;
		if(can<leftover) continue;
		can-=leftover;
		if(losun+can!=p) continue;
		
		auto af=[&](int tar)->bool{
			losun=0,can=0;
			rep(i,si){
				if(!cntt[i]) continue;
				int x=cntt[i]/blocks;
				int hi=min(x,(cnts[i]-cntt[i])/tar);
				// x >= cntt[i] - x * blocks 
				// x*(blocs+1)>=cntt[i]
				int lo=cntt[i]/(blocks+1);
				// in pattern i occurs in range [lo ... hi]
				if(hi<lo) return 0;
				losun+=lo;
				can+=hi-lo;
			}
			// print(can,leftover,losun);
			return can>=leftover and losun+can-leftover>=p;
		};

		// if(p==2) print(af(1));
		int lf=1,rg=n;
		int opt=0;
		while(lf<=rg){
			int md=(lf+rg)/2;
			if(af(md)) opt=md,lf=md+1;
			else rg=md-1;
		}
		ans=max(ans,opt+1);
	}
	print(ans);
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t;
	cin>>t;
	rep(cs,t){
		slv();
	}
}