#include <bits/stdc++.h>

int main() {
    //freopen("in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int ttt;
    std::cin >> ttt;
    while (ttt--) {
        std::string x, y;
        std::cin >> x >> y;
        std::vector<int> s(26), t(26);
        for (auto &c: x)
            ++s[c - 'a'];
        for (auto &c: y)
            ++t[c - 'a'];
        bool flag = 0;
        for (int i = 0; i < 26; ++i) {
            if (s[i] < t[i]) {
                puts("0");
                flag = 1;
                break;
            }
        }
        if (flag)
            continue;
        int min = std::min(x.length(), y.length());
        int ans = 1;
        for (int k = 2; k <= min; ++k) {
            bool f = 0;
            int tmp = 1e9 + 7;
            for (int i = 0; i < 26; ++i) {
                if (!t[i])
                    continue;
                if (t[i] + 1 < k) {
                    f = 1;
                    break;
                }
                int p = (t[i] + k - 1) / k;
                tmp = std::min(tmp, 1 + (s[i] - t[i]) / p);
                //printf("tmp %d\n", tmp);
            }
            if (!f)
                ans = std::max(ans, tmp);
        }
        printf("%d\n", ans);
    }
    return 0;
}