#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
inline bool Check(vector<int> tmax, vector<int> tcnt) {
    static int period[N];
    static int uniq[N];
    int req = 26;
    int mx = 0;
    // for (auto x : tmax) cerr << x << ' ';
    // cerr << endl;
    // for (auto x : tcnt) cerr << x << ' ';
    // cerr << endl;
    for (int d = 0; d < 26; ++d) {
        if (!tcnt[d]) { req -= 1; continue; }
        static vector<int> X;
        X.clear();
        for (int tm = min(tmax[d], tcnt[d] + 1); tm; --tm) {
            int x = tcnt[d] / tm;
            mx = max(mx, x);
            X.push_back(x);
            if (tcnt[d] % tm == 0 && x) {
                X.push_back(x - 1);
            }
        }
        for (auto x : X) uniq[x] = 1;
        for (auto x : X) period[x] += uniq[x], uniq[x] = 0;
    }
    bool flag = 0;
    for (int x = 0; x <= mx; ++x) {
        if (period[x] == req) flag = 1;
        period[x] = 0;
    }
    return flag;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int Case;
    cin >> Case;
    while (Case--) {
        string s, t;
        cin >> s >> t;
        vector<int> scnt(26), tcnt(26);
        for (auto c : s) ++scnt[c - 'a'];
        for (auto c : t) ++tcnt[c - 'a'];
        bool flag = 1;
        for (int i = 0; i < 26; ++i) {
            if (scnt[i] < tcnt[i]) flag = 0;
        }
        if (!flag) { cout << "0\n"; continue; }
        int ans = 0;
        for (int l = 1, r = s.size(); l <= r; ) {
            int mid = (l + r) >> 1;
            vector<int> tmax(26);
            for (int i = 0; i < 26; ++i) {
                tmax[i] = (scnt[i] - tcnt[i]) / mid;
            }
            // cerr << mid << endl;
            if (Check(tmax, tcnt)) ans = mid, l = mid + 1; else r = mid - 1;
        }
        cout << ans + 1 << '\n';
    }
    return 0;
}