#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ll long long
const int mod=998244353;
const int inf=0x3f3f3f3f;
string s,t;
int n,m;
int cs[26],ct[26],lim[26];
bool chk(int occ)
{
	for(int i=0;i<26;i++) if(ct[i])
	{
		if(cs[i]<ct[i]) return 0;
		if(occ>1){
			lim[i]=(cs[i]-ct[i])/(occ-1);
			lim[i]=ct[i]-lim[i];
		}
		else lim[i]=0;
	}
	if(occ==1)return 1;
	int sum=0,ok1=1;
	for(int i=0;i<26;i++)if(ct[i]){
		if(lim[i]*2>ct[i]) ok1=0;
		sum+=lim[i];
	}
	if(ok1&&sum<=m/2) return 1;
	for(int len=m/2+1;len<m;len++){
		int sm=m-len,x=m/sm,ck=m%sm;
		bool fl=0;
		ll sb=0,ks=0;
		for(int i=0;i<26;i++)if(ct[i]){
			ll b_=ct[i]%x,kl=0,a_=(ct[i]-b_)/x-b_;
			if(a_<0){fl=1;break;}
			ll kr=a_/(x+1);
			kl=max(kl,lim[i]-b_*x-a_*(x-1));
			if(kl>kr){fl=1;break;}
			sb+=b_+kl*x,ks+=kr-kl;
		}
		if(!fl&&sb<=ck&&(ck-sb)%x==0&&(ck-sb)/x<=ks)
			return 1;
	}
	return 0;
}
int nd[26],tot[26];
void solve()
{
	cin>>s>>t;
	memset(cs,0,sizeof(cs)),memset(ct,0,sizeof(ct)),memset(nd,0,sizeof(nd)),memset(tot,0,sizeof(tot));
	int flg=1;
	for(int i=0;i+1<t.size();i++) if(t[i]!=t[i+1]) 
	{
		flg=0;
		break;
	}
	n=s.size(),m=t.size();
	for(int i=0;i<n;i++) cs[s[i]-'a']++;
	for(int i=0;i<m;i++) ct[t[i]-'a']++,nd[t[i]-'a']++,tot[t[i]-'a']++;
	if(flg)
	{
		cout<<max(0,cs[t[0]-'a']-m+1)<<"\n";
		return;
	}
	int L=1,R=n,res=0;
	while(L<=R){
		int mid=(L+R)>>1;
		if(chk(mid)) res=mid,L=mid+1;
		else R=mid-1;
	}
	cout<<res<<"\n"; 
}
//(a+b)x+b=c

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}