#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;



int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int q;
    cin >> q;

    for (int qq = 1; qq <= q; qq++) {
        string s, t;
        cin >> s >> t;

        vector<int> frs(26);
        for (auto ch : s) {
            frs[ch - 'a']++;
        }
        vector<int> frt(26);
        for (auto ch : t) {
            frt[ch - 'a']++;
        }

        bool bad = false;
        for (int ch = 0; ch < 26; ch++) {
            if (frt[ch] > frs[ch]) {
                bad = true;
            }
        }

        if (bad) {
            cout << 0 << "\n";
            continue;
        }

        int answer = 0;
        for (int k = 1; k <= t.size(); k++) {
            int curr = s.size();
            bool ok = true;
            for (int ch = 0; ch < 26; ch++) {
                if (frt[ch] == 0) continue;

                // frt[ch] = x * k + y, x >= y
                // frt[ch] <= x * (k + 1)

                int x = (frt[ch] + k) / (k + 1);
                int y = frt[ch] - x * k;
                while (x < y) {
                    x++;
                    y -= k;
                }

                if (x < y || y < 0) {
                    ok = false;
                    break;
                }

                curr = min(curr, 1 + (frs[ch] - frt[ch]) / x);
            }

            if (ok) {
                answer = max(answer, curr);
            }
        }

        cout << answer << "\n";
    }

    return 0;
}