#include <bits/stdc++.h>

using namespace std;

using ll = long long;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int tests;
    cin >> tests;
    while (tests--) {
        string t, s;
        cin >> t >> s;
        vector<int> cs(26), ct(26);
        for (auto i: t) ct[i - 'a']++;
        for (auto i: s) cs[i - 'a']++;
        bool fl = true;
        for (int i = 0; i < 26; ++i)
            if (ct[i] < cs[i]) {
                cout << 0 << '\n';
                fl = false;
            }
        if (!fl)
            continue;
        int n = (int)s.size(), ans = 0;
        for (int l = 1; l <= n; ++l) {
            int mn = 1e9;
            for (int i = 0; i < 26; ++i) {
                if (cs[i] == 0)
                    continue;
                int cnt = (cs[i] + l - 1) / l;
                if (cnt * (l - 1) > cs[i])
                    mn = -1e9;
                else
                    mn = min(mn, ct[i] - cs[i] / cnt);
            }
            ans = max(ans, 1 + mn);
        }
        cout << ans << '\n';
    }
}