#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']++;
        int g = 0;
        for (auto i : cs) g = gcd(g, i);
//        cout << g << endl;
        int cc = 1e9;
        for (int i = 0; i < 26; ++i) {
            if (cs[i] == 0) continue;
            cc = min(cc, ct[i] / (cs[i] / g));
        }
        cout << max(0, cc - g + 1) << '\n';
    }
}