#include <iostream>
#include <string>
#include <vector>

void solve() {
    std::string s, t;
    std::cin >> s >> t;
    std::vector<int> a(26), b(26);

    for (char c : s) {
        a[c - 'a']++;
    }
    for (char c : t) {
        b[c - 'a']++;
    }


    int ans = 0;
    for (int i = 1; i <= t.size(); i++) {
        bool ok = true;
        int min = s.size();
        for (int j = 0; j < 26; j++) {
            if (b[j] == 0) {
                continue;
            }
            int q = b[j] / i;
            int max = 0;
            while (q >= 1) {
                int r = b[j] - q * i;
                if (r > q) {
                    break;
                }
                max = std::max(max, a[j] / q + (a[j] % q >= r) - 1);
                q--;
            }
            // std::cout << i << " " << a[j] << " " << b[j] << " " << max << std::endl;
            min = std::min(min, max);
        }
        if (ok) {
            // std::cout << i << " " << min << std::endl;
            ans = std::max(ans, min - i + 1);
        }
    }

    std::cout << ans << std::endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}