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

int main() {
    static const int maxn = 2000010, sigma_size = 26;
    int z;
    scanf("%d", &z);
    while (z--) {
        static char s[maxn], t[maxn];
        scanf("%s %s", s, t);
        int ls = strlen(s), lt = strlen(t);
        static int cS[sigma_size], cT[sigma_size];
        memset(cS, 0, sizeof(cS)), memset(cT, 0, sizeof(cT));
        for (int i = 0; i < ls; i++) cS[s[i] - 'a']++;
        for (int i = 0; i < lt; i++) cT[t[i] - 'a']++;
        int g = 0;
        for (int i : cT) g = __gcd(g, i);
        int mx = 0;
        if (g != 1) {
            mx = INT_MAX;
            for (int i = 0; i < sigma_size; i++)
                if (cT[i])
                    mx = min(mx, cS[i] / (cT[i] / g));
            mx = max(0, mx - g + 1);
        }
        for (int c = 1; c <= lt; c++) {
            int cur = INT_MAX;
            for (int i = 0; i < sigma_size; i++) {
                if (!cT[i])
                    continue;
                int p = (cT[i] + c) / (c + 1), q = cT[i] - p * c;
                cur = min(cur, (cS[i] - q) / p);
            }
            mx = max(mx, cur - c + 1);
        }
        printf("%d\n", mx);
    }
    return 0;
}