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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e6;

int N, M, TC;
char S[MAXN+10], T[MAXN+10];
int A[30], B[30];

int main()
{
    scanf("%d", &TC);
    while(TC--)
    {
        scanf(" %s %s", S+1, T+1);
        N=strlen(S+1);
        M=strlen(T+1);

        for(int i=0; i<26; i++) A[i]=B[i]=0;
        for(int i=1; i<=N; i++) A[S[i]-'a']++;
        for(int i=1; i<=M; i++) B[T[i]-'a']++;

        bool flag=true;
        for(int i=0; i<26; i++)
        {
            if(A[i]<B[i]) flag=false;
            else A[i]-=B[i];
        }
        if(!flag)
        {
            printf("0\n");
            continue;
        }
        
        int ans=0;
        for(int i=1; i<=M; i++)
        {
            bool flag=true;
            int val=N;
            for(int j=0; j<26; j++)
            {
                int x=(B[j]+i)/(i+1);
                int y=B[j]-x*i;
                if(x<y)
                {
                    flag=false;
                    break;
                }
                if(x) val=min(val, A[j]/x);
            }
            if(flag) ans=max(ans, val);
        }
        printf("%d\n", ans+1);
    }
}