#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int a[35],b[35],f[N],g[N];
int main(){
	int n;
	string s,t;
	cin>>n;
	while(n--){
		cin>>s>>t;
		int lens=s.length(),lent=t.length(),ans=0;
		for(int i=1; i<=lent; i++)f[i]=N,g[i]=0;
		for(int i=0; i<26; i++)a[i]=0,b[i]=0;
		for(int i=0; i<lens; i++)a[s[i]-'a']++;
		for(int i=0; i<lent; i++)b[t[i]-'a']++;
		int cnt=0;
		for(int i=0; i<26; i++){
			if(b[i]==0){
				cnt++;
				continue;
			}
			int mx=0;
			int xx=0,yy=0;
			for(int j=1; j<=b[i]; j++){
				int x=a[i]/j-b[i]/j+(b[i]%j<=a[i]%j),y=(b[i]-1)/j+1;
				if(y!=yy){
					f[yy]=min(f[yy],xx);
					g[yy]++;
					xx=x;
					yy=y;
				}
				else xx=max(xx,x);
			}
			f[yy]=min(f[yy],xx),g[yy]++;
		}
		for(int i=1; i<=lent; i++)if(g[i]==26-cnt)ans=max(ans,f[i]);
		cout<<ans<<endl;
	}
}