#include<bits/stdc++.h>
using namespace std;
int T,t[33],h[33];
char c[2000100],s[2000100];
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%s",c+1);
        int l=strlen(c+1); int o=l;
        for(int i=0;i<=30;i++) t[i]=h[i]=0;
        for(int i=1;i<=l;i++) {
            t[c[i]-'a']++;
        }
        scanf("%s",s+1);
        l=strlen(s+1);
        for(int i=1;i<=l;i++) {
            h[s[i]-'a']++;
        }
        bool flag=1;
        for(int i=0;i<26;i++) {
            if(h[i]>t[i]) {
                flag=0;
                break;
            }
        }
        if(!flag) {
            printf("0\n");
            continue;
        }
        for(int i=0;i<26;i++) t[i]-=h[i];
        int minl=l;
        for(int i=0;i<26;i++) {
            if(h[i]>0) minl=min(h[i],minl); 
        }
        int res=0;
        for(int i=1;i<=minl;i++) {
            int ans=o;
            for(int j=0;j<26;++j) {
                if(h[j]==0) continue;
                if(h[j]%(i+1)) {
                    int r=(h[j]/(i+1))+1;
                    ans=min(ans,t[j]/r);
                } else {
                    int r=h[j]/(i+1);
                    ans=min(ans,t[j]/r);
                }
            }
            res=max(res,ans);
        }
        printf("%d\n",res+1);
    }
    return 0;
}