#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define mem(a) memset(a,0,sizeof(a))
const int N=100005;
int t,n;
int S[26],T[26];
int check(int x){
int ans=0;
For(cs,1,n)if(n%i==0){
int sum=0,flag=0,gb=1e9;
For(i,0,25){
int ab=min(S[i]/x,T[i]/cs),b=T[i]-ab*cs;
//if(x==2&&cs==1&&i+'a'=='l')cerr<<ab<<" "<<S[i]<<" "<<b<<endl;
if(b>ab)flag=1;
}
//if(x==2&&flag==0)cout<<cs<<" "<<flag<<endl;
if(flag)continue;
return 1;
}
return 0;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>t;
while(t--){
string s,t;
cin>>s>>t;
mem(S); mem(T);
for(auto i:s)S[i-'a']++;
for(auto i:t)T[i-'a']++;
For(i,0,25)S[i]-=T[i];
int flag=0;
For(i,0,25)if(S[i]<0){
cout<<0<<endl; flag=1; break;
}
n=t.length();
if(flag)continue;
int l=0,r=s.length();
while(l<r){
int mid=(l+r)>>1; mid++;
if(check(mid))l=mid; else r=mid-1;
}
cout<<1+l<<endl;
}
}