#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 = 1; k <= min + 1; ++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, q;
                if (k == 1) {
                    p = 1;
                } else {
                    p = t[i] / (k - 1);
                    q = t[i] % (k - 1);
                    int z = (p - q) / k;
                    p += z;
                    q += z * (k - 1);
                }
                tmp = std::min(tmp, 1 + (s[i] - t[i]) / p);
                //printf("tmp %d\n", tmp);
            }
            if (!f) {
                //std::cout << k << ' ' << tmp << std::endl;
                ans = std::max(ans, tmp);
            } else {
                break;
            }
        }
        std::cout << ans << std::endl;
    }
    return 0;
}