#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int z;
    cin >> z;
    while (z--) {
        string s, t;
        cin >> s >> t;
        vector<int> cnts(26), cntt(26);
        for (char c : s) {
            ++cnts[c - 'a'];
        }
        for (char c : t) {
            ++cntt[c - 'a'];
        }
        int g = 0;
        rep(c, 0, 26) { g = gcd(g, cntt[c]); }
        if (g == 1) {
            int maxA = 1e9, maxB = 1e9;
            rep(c, 0, 26) {
                if (cntt[c] / 2) {
                    chmin(maxA, cnts[c] / (cntt[c] / 2));
                }
                if (cntt[c] % 2) {
                    chmin(maxB, cnts[c]);
                }
            }
            cout << max(0, min(maxA - 1, maxB)) << "\n";
        } else {
            int maxA = 1e9;
            rep(c, 0, 26) {
                if (cntt[c] != 0) {
                    chmin(maxA, cnts[c] / (cntt[c] / g));
                }
            }
            cout << max(0, maxA - g + 1) << "\n";
        }
    }
}