#include <bits/stdc++.h>
using namespace std;

const int N=2e6+5;

int n,m;
char s[N],t[N];
int c1[26],c2[26],x[26];

inline bool check(int k)
{
	for(int i=0;i<26;i++)
	{
		int lef=(c2[i]+k)/(k+1);
		int rig=c2[i]/k;
		if(lef>rig) return false;
		x[i]=lef;
	}
	return true;
}

inline int ask()
{
	int ans=1e9;
	for(int i=0;i<26;i++)
		if(x[i])
			ans=min(ans,c1[i]/x[i]);
	return ans;
}

int main() {
	//ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%s",s+1);
		scanf("%s",t+1);
		n=strlen(s+1);
		m=strlen(t+1);
		for(int i=0;i<26;i++) c1[i]=c2[i]=0;
		for(int i=1;i<=n;i++) c1[s[i]-'a']++;
		for(int i=1;i<=m;i++) c2[t[i]-'a']++;
		bool flag=true;
		for(int i=0;i<26;i++)
			if(c1[i]<c2[i])
			{
				flag=false;
				break;
			}
			else 
				c1[i]-=c2[i];
		if(!flag)
		{
			printf("0\n");
			continue;
		}
		int ans=0;
		for(int i=1;i<=m;i++) 
			if(check(i))
			{
				ans=max(ans,1+ask());
			}
		printf("%d\n",ans);
	}
	return 0;
}