#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);
        if (g != 1) {
            int mx = INT_MAX;
            for (int i = 0; i < sigma_size; i++)
                if (cT[i])
                    mx = min(mx, cS[i] / (cT[i] / g));
            printf("%d\n", max(0, mx - g + 1));
            continue;
        }
        int mx = INT_MAX;
        for (int i = 0; i < sigma_size; i++) {
            if (!cT[i])
                continue;
            int cA = cT[i] >> 1, cB = cT[i] & 1;
            mx = min(mx, (cS[i] - cA) / (cA + cB));
        }
        printf("%d\n", max(0, mx));
    }
    return 0;
}