/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#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
const int mod=998244353;
const int inf=0x3f3f3f3f;
string s,t;
int cs[26],ct[26],nd[26],tot[26];
int getcost(int x)
{
	if(!nd[x]) return inf;
	if(cs[x]<tot[x]) return 0;
	return 1+(cs[x]-tot[x])/nd[x];
}
int calc()
{
	int res2=inf;
	for(int i=0;i<26;i++) if(nd[i]) res2=min(res2,getcost(i));
	return res2;
}
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;
	}
	int 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 tr=0;
	int res=calc();
	while(1)
	{
		tr++;
		if(tr==n) break;
		int minn=inf,id=-1;
		for(int i=0;i<26;i++) if(getcost(i)<minn) minn=getcost(i),id=i;
		if(tr<=m/2)
		{
			if(ct[id]<2) break;
			nd[id]--,ct[id]-=2;
			res=max(res,calc());
		}
		if(!ct[id]) break;
		ct[id]--;
		int ok=1;
		int k=n-tr;
		int len1=(n+k-1)/k,len2=len1-1;
		int cnt1=0,cnt2=0;
		for(int i=0;i<26;i++)
		{
			int has=tot[i]-ct[i];
			if(!has) continue;
			cnt1+=has%len2,cnt2+=len2-has%len2;
		}
		int nd1=m%len2,nd2=m-m%len2;
		if(cnt1<nd1||cnt2<nd2) ok=0;
		nd[id]--;
		if(ok) res=max(res,calc());
//		for(int i=0;i<26;i++) cout<<nd[i]<<" ";
//		cout<<"\n";
	}
	
	cout<<res<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}